D: Median of Medians - AtCoder Regular Contest 101 | AtCoder

中央値がxの場合=>中央値がx以上の場合

f(x) := 「x以上の値が中央値となる連続部分列の個数」とする。 ここで部分列がH(N, 2)個あるので、そのちょうど真ん中になるのが中央値。 つまり f(x) >= ceil(H(N, 2)/2) を満たす最大のxが解。fは単調増加なので二分探索が使える。

x以上の値が中央値となる連続部分列を数える

二分探索で条件を固定することで、入力を単純にとらえられる。 x以上の値とx未満の値かどうかだけをみる。前者が半数以上となるような 連続部分列は中央値がx以上である。 前者を+1, 後者を-1とすると、連続部分列の和が0以上ならば、中央値がx以上となるはず。 この数列をCとする。 とりあえず累積和を求めておく S[i] = Σ_{0<=j<=i}C[j]とすると [l, r)の部分和は S[r]-S[l]であり、中央値の条件は S[r]-S[l]>=0つまり S[r]>=S[l] よって、rを小さいほうから見ていって、Binary Indexed TreeなどでS[l]を数えていけばいい。

const int MAX_N = 100005;
int N, A[MAX_N], B[MAX_N];

// sm(C[i]), sorted
int S[MAX_N], T[MAX_N];

// 和のインデックス(BITで使う)
int g(int y) {
    return lower_bound(T, T + N + 1, y) - T;
};

ll f(int x) {
    // S[r]-S[l]>=0
    // を満たすようなS[l]の数
    BinaryIndexedTree<int> bit(N + 1);
    int b = B[x];

    rep(i, N) {
        int c = A[i] >= b ? 1 : -1;
        T[i + 1] = S[i + 1] = S[i] + c;
    }

    sort(T, T + N + 1);

    ll cnt = 0;
    bit.add(g(0), 1);
    rep(i, N) {
        int j = g(S[i + 1]);
        cnt += bit.sum(0, j + 1);
        bit.add(j, 1);
    }

    return cnt;
}

void solve() {
    cin >> N;
    rep(i, N) {
        cin >> A[i];
        B[i] = A[i];
    }

    sort(B, B + N);
    int M = unique(B, B + N) - B;

    // ceil(H(N,2)/2)
    // = ceil(N*(N+1)/4)
    // オーバーフロー注意!!
    ll need = (N*(N + 1ll) + 3) / 4;

    int ok = 0, ng = M;
    while (ng - ok > 1) {
        int mid = (ok + ng) / 2;
        if (f(mid) >= need) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    cout << B[ok] << endl;
}