ARC101 D - Median of Medians

問題

長さnの数列aが与えられる
この数列の全ての連続する部分列の中央値を並べ、新しい数列mを作る
数列mの中央値を求める

1 <= n <= 10^5
1 <= a[i] <= 10^9

解法

(思考)
各要素が中央値になるような区間が何個あるかわかると嬉しい
→値aが中央値になるような区間っていうのは、(区間に含まれるa以下の値の個数)-(a超過の値の個数)=1 となるような区間
→これを全要素について求めるのは難しい(O(N^2)かかっちゃう)
→二分探索でO(NlogN)に落とせる

二分探索で求めるのは「k以下の値が中央値になるような区間の個数が、数列mの長さの半分を超える」ようなkの下限
判定にはBITを使った
数列aのk以下の要素を1、kを超える要素を-1として手前から和をとっていく
今の和がsumのとき、今見ている要素を右端とするような条件を満たす区間の個数は、その要素の左側にある「和がsum未満になった場所」の個数に等しい
(累積和と考えれば理由はわかる)

実装

最初に数列aを圧縮した
map cで圧縮し、答えを出力するときにdで元に戻す
区間を数え上げるときはsumが負になることもあるから適当な数字(114514)を足して使う

ちなみに俺は本番中ずっとcntメソッド内でサイズ2^20のBITを宣言してスタックオーバーフローしてたらしい
BITがバグってるのかな？とか(最近エディタ変えたから)俺の環境がおかしいのかな？とか悩んでたのがほんとにアホくさい
その後グローバルに置いたから判定ごとに中身を0に初期化してる

#define int long long

template<class T, int ME> class BIT {
	public:
	T bit[1<<ME],val[1<<ME];
	T sum(int e) {T s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	T add(int e,T v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	T set(int e,T v) { add(e,v-val[e]);}
	int lb(T v) {
		T tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<v) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};

int n, a[100100], m, l = -1, r;
map<int,int> c, d;
set<int> s;
BIT<int,20> f;

int cnt(int k) {
	int sum = 0, ret = 0;
	reps(i,-100100,100100) f.set(i+114514,0);
	f.add(114514,1);
	rep(i,n) {
		sum += (a[i]<=k ? 1 : -1);
		f.add(sum+114514,1);
		ret += f.sum(sum+114513);
	}
	return ret;
}

signed main() {
	cin >> n;
	rep(i,n) cin >> a[i];
	rep(i,n) s.insert(a[i]);
	each(i,s) c[i] = m, d[m] = i, m++;
	rep(i,n) a[i] = c[a[i]];
	r = m-1;
	while (r-l>1) {
		int md = (l+r)/2;
		if (cnt(md) > n*(n+1)/4) r = md;
		else l = md;
	}
	cout << d[r] << endl;
}