AtCoder Regular Contest 101：D - Median of Medians

問題
解法
解答

問題

長さ N の数列 a の全ての連続する部分列の中央値を集めた数列の中央値を求める問題．

解法

以下の２つの条件を満たす x は数列の中央値になる：

数列の中に x 以上の要素が半分以上含まれる

x は 1. を満たす整数の中で最大

なので，1. を満たす最大の要素を二分探索で見つければよい．

数列 a の要素を x 以上のものであれば +1，未満のものであれば -1 と置き換えると，a の部分列が x 以上のものを半分以上含んでいるかどうかわかりやすい（部分列の和が 0 以上になっていればよいので）．ここで，累積和をとっておくと部分列の和が求めやすくなる．部分列の和が 0 以上になるためには，その部分列の前までの和がその部分列の最後要素までの和以下になっていればよいので，これは BIT を用いて何通りあるか数えられる．