Median of Medians [AtCoder Regular Contest 101 D]

https://beta.atcoder.jp/contests/arc101/tasks/arc101_b

前提知識

• 二分探索

解法

https://beta.atcoder.jp/contests/arc101/submissions/3082371

答えで二分探索する。
check(x) := 全ての区間の中で中央値がx以上のものが過半数超えているか
全ての区間の中で中央値がx以上のものが何個あるか数えて、過半数超えしているか判定する。
　
まずは、条件を言い換えよう。
中央値がx以上という条件は、x以上の数が過半数を超えていると言い換えられる。
ここで、x以上の数を+1, x未満を-1と置き換えて考えてみる。
すると、更に全体の総和が0以上であると中央値がx以上と言える。
　
この条件をうまく使って数え上げをしていくが、
「区間の数え上げは右端を固定して、有効な左端を数える」という頻出テクを使う。
右端をi, その時の先頭からの+1,-1の累積和をtot[i]とすると、0≦tot[i]-tot[j]かつj＜iであるjの個数を数えたい。
tot[j]≦tot[i]と不等式が言い換えられるので、今までのtotの個数をBITを使って集計しておけば高速に求まる。
　
全ての区間はN*(N-1)/2+Nあるので、過半数を超えるにはこの半分以上であるかを見ればいい。
半分以上であることを見るには2で割ったときに切り上げる必要があるが、そのために+1を追加でしている。
※kで割った切り上げが欲しいときは x / kではなく (x + k-1) / kとすれば求められるテク

int offset = 100000;
int N, A[101010];
//---------------------------------------------------------------------------------------------------
int check(int x) {
    BIT<int> bit(201010);
 
    ll sm = 0;
    int tot = 0;
    bit.add(offset, 1);
    rep(i, 0, N) {
        if (x <= A[i]) tot++;
        else tot--;
 
        sm += bit.get(0, tot + offset + 1);
        bit.add(tot + offset, 1);
    }
 
    return (1LL * N * (N - 1) / 2 + N + 1) / 2 <= sm;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    int ok = 0, ng = inf;
    while (ok + 1 != ng) {
        int md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}