ARC #101 D
長さ \(M\) の数列の中央値は, 以下の性質を持つ.
- ある数 \(x\) について, 数列内に \(x\) 以上の数は \(\lceil M/2 \rceil\) 個以上ある.
- そのような数 \(x\) の最大値が中央値である.
このような \(x\) を二分探索で求めることを考える.
さて, \(x\) を仮定すると, その \(x\) について,
\(a[l, r] \ (1 \leq l \leq r \leq N)\) の中に \(x\) 以上の数が \(\lceil (r-l+1)/2 \rceil\) 個以上あるような \(l, r\) の組み合わせが \(\lceil N(N+1)/4 \rceil\) 個以上あるか?
という問題になる. ここでは前半の
\(a[l, r] \ (1 \leq l \leq r \leq N)\) の中に \(x\) 以上の数が \(\lceil (r-l+1)/2 \rceil\) 個以上あるような \(l, r\) の組み合わせは何通りか?
の部分について考える. \(a_i\) は \(x\) 以上かどうかだけ分かればいいので, \(x\) 以上の場合を \(+1\), \(x\) 未満の場合を \(-1\) とすると,
\(a[l, r]\) の総和が非負になるような \(l, r\) の組み合わせは何通りか?
という問題に置き換えられる. 総和を求めるには累積和が使える. \(a_1\) から \(a_i\) 番目の要素までの総和を \(S_i\) とすると,
\(S_r-S_l \geq 0 \ (0 \leq l \lt r \leq N)\) となるような \(l, r\) の組み合わせは何通りか?
という問題になり, これを変形して,
\(S_l \leq S_r \ (0 \leq l \lt r \leq N)\) となるような \(l, r\) の組み合わせは何通りか?
という問題になる. これは転倒数を求める問題と非常によく似ているので, Fenwick Tree を使って \(O(N\log N)\) で求められる.