AtCoder Regular Contest 028 - B 特別賞

別解法シリーズ．別解で通すのは楽しいよ．

問題

arc028.contest.atcoder.jp

解説解法

priority_queue を使う．既に K 番目以下の人を priority_queue に入れず無視する点がひらめきのミソ．

脳筋解法

BIT と 二分探索 を使う．

idxを1から順に増やしていき，答えを更新していくことを考える．

i位の人がa番目に若いとき，bit[a] に1を加算する．

『1からx番目の区間に1がいくつあるか』は，『x番目以下に若い人が何人現れたか』である．

計算量は O(N(logN)^2)

Submission #1612176 - AtCoder Regular Contest 028 | AtCoder

ll m, n, kei;
 
ll aa[100010];
ll bb[100010];
 
int main() {
 
    scanner >> n >> kei;
 
    repeat(i, n) {
        int a;
        scanner >> a;
        aa[i] = a;
        bb[a] = i+1;
    }
 
    int idx = 0;
 
    bitree<int> bit(n+1);
    for (; idx < kei - 1; ++idx) {
        bit.add(aa[idx], 1);
    }
 
    for (; idx < n; ++idx) {
        bit.add(aa[idx], 1);
        ll p = b_search(0ll, n, [&](ll x) { return kei <= bit.sum(x); });
        printf("%lld\n", bb[p]);
    }
 
 
    return 0;
}