ARC101B Median of Medians - 二分 - 树状数组 -

题目链接：https://atcoder.jp/contests/arc101/tasks/arc101_b

题解：
直接求序列的中位数不好求，考虑分析性质：
设\(b_i = (-1) ^{[a_i \geq k]}\)，如果\([l,r]\)的中位数小于 k，那么b的和一定大于0，而且这个和一定随k增大而增大
这个单调性启示我们可以对外层的中位数二分答案
但是直接统计b的区间和是\(O(n^2)\)的，不符合要求，考虑前缀和优化
\(b[l..r] >= 0\) 等价于 \(s[r] - s[l-1] >= 0, s[r] >= s[l-1]\)，因此对于每一个r，考虑统计s值更小的顺序对，这可以用树状数组简单实现

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn =2e5+10, bs = 1e5+1;

int n,a[maxn],bit[maxn],sum[maxn];
int lb(int x){return x & (-x);}
int query(int x){
	int r = 0;
	for(int i = x;i;i-=lb(i))r += bit[i];
	return r;
}

void upd(int x){
	for(int i=x;i<=maxn - 5;i+=lb(i))++ bit[i];
}

int check(int k){
	LL r = 0;
	for(int i=0;i<=maxn - 5;i++)bit[i] = 0;
	for(int i=1;i<=n;i++)sum[i] = a[i] >= k ? -1 : 1;
	for(int i=2;i<=n;i++)sum[i] += sum[i-1];
	for(int i=1;i<=n;i++)r += sum[i] > 0 ? 1 : 0; 
	
	for(int i=1;i<=n;i++)
		r += query(sum[i] - 1 + bs), upd(sum[i] + bs);
	
	return r <= 1ll * n * (n+1) / 4;
}

signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int l=1, r=1e9, ans;
	while(l <= r){
		int mid = l+r>>1;
		if(check(mid))l = mid+1, ans = mid;
		else r = mid-1;
	}
	printf("%d\n",ans);

	return 0;
}