長さ \(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)\) で求められる.