はまやんはまやんはまやん

hamayanhamayan's blog

プログラミングコンテスト II [パソコン甲子園2016 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0343?year=2016

前提知識

考察過程

1. (平衝二分木でset作れば一発っぽいが…)
2. (パソコン甲子園で平衝二分木実装して通したらかっこいい)
3. クエリ先読みしていろいろやる問題だろうと仮定
4. 回答クエリから考えてみる
5. m番目のチームを答えるが、k点以上のチーム数を高速に求められるようにしておいて二分探索できそう
6. クエリ先読み+座圧+BITでk点以上のチーム数を高速に求めるのはできそう
7. あとは、k点取ってるチームの中でどのチームが答えかを判定する部分
8. これも点数毎にBITを持って、二分探索すればできそう
9. 計算量が心配だが、O(Nlog^2N)っぽいので大丈夫でしょ(BITのlogだし)
10. 実装がむっちゃ重いがやると通る
11. (平衝二分木の方が実装軽いまである)

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0343/judge/3140257/C++14

クエリ先読みして事前準備をしてからクエリ処理に取り掛かる。
 
// for zaatsu
まず、出てくるポイントを全て取得して座圧しよう。
「point[i] := チームiのポイント」を使って、出てくるポイントを集計して、座圧したものを準備する。
 
// make idx and bits
次に、各ポイントになるチームを集計する。
idx[i] := ポイントがiとなる瞬間のあるチームの集合
ポイントiは座圧したものを使おう。
idx[0]には0~N-1をすべて入れておく。
idx[i]を作ったらソートしておき、その大きさに対応したbitを作る。
 
// do
シミュレートしながら、答えておこう。
BITを用意するが、2つ使う。
bit[i] := ポイントがiであるチーム数
bits[i][j] := ポイントがiであるチームの中でチームjの現在ポイントがiであるか
最初の状態として、

  • bit[0] = N:ポイント0のチームがNチーム
  • bits[0][0] = bits[0][1] = bits[0][1] = ... :全てのチームがポイント0に属している

とする。
 
加算クエリでは、現在のポイントでbit,bitsを消して、加算後のポイントでbit,bitsを作る。
 
回答クエリでは、まずは答えとなるポイントを二分探索で求めよう。
これはbitを使えば実現できる。
答えとなるポイントが見つかれば、そのポイントの中の何番目のチームかも、二分探索で求めよう。
あとは、それで答えれば答え。

int N, C;
int type[101010], a0[101010], a1[101010];
ll point[101010];
vector<ll> z; int nz;
vector<int> idx[101010];
BIT<int> bit;
BIT<int> bits[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C;
    z.push_back(0);
    rep(c, 0, C) {
        cin >> type[c];
        if (type[c] == 0) {
            cin >> a0[c] >> a1[c];
            a0[c]--;
        }
        else cin >> a0[c];
    }

    // for zaatsu
    rep(c, 0, C) if(type[c] == 0) {
        point[a0[c]] += a1[c];
        z.push_back(point[a0[c]]);
    }
    sort(all(z));
    z.erase(unique(all(z)), z.end());
    nz = z.size();
    bit.init(nz);

    // make idx and bits
    rep(i, 0, N) point[i] = 0;
    rep(c, 0, C) {
        if (type[c] == 0) {
            point[a0[c]] += a1[c];
            int i = lower_bound(all(z), point[a0[c]]) - z.begin();
            idx[i].push_back(a0[c]);
        }
    }
    rep(i, 0, N) idx[0].push_back(i);
    rep(i, 0, nz) {
        sort(all(idx[i]));
        bits[i].init(idx[i].size());
    }

    // do
    rep(i, 0, N) point[i] = 0;
    bit.add(0, N);
    rep(i, 0, N) bits[0].add(i, 1);
    rep(c, 0, C) {
        if (type[c] == 0) {
            int id, id2;

            id = lower_bound(all(z), point[a0[c]]) - z.begin();
            bit.add(id, -1);
            id2 = lower_bound(all(idx[id]), a0[c]) - idx[id].begin();
            bits[id].add(id2, -1);
            
            point[a0[c]] += a1[c];
            
            id = lower_bound(all(z), point[a0[c]]) - z.begin();
            bit.add(id, 1);
            id2 = lower_bound(all(idx[id]), a0[c]) - idx[id].begin();
            bits[id].add(id2, 1);
        } else {
            int ok = 0, ng = nz;
            while (ok + 1 != ng) {
                int md = (ng + ok) / 2;
                if (a0[c] <= bit.get(md, nz)) ok = md;
                else ng = md;
            }
            
            int id = ok;
            a0[c] -= bit.get(ok + 1, nz);

            ng = 0, ok = idx[id].size();
            while (ng + 1 != ok) {
                int md = (ng + ok) / 2;
                if (a0[c] <= bits[id].get(0, md)) ok = md;
                else ng = md;
            }


            int id2 = ok - 1;

            printf("%d %lld\n", idx[id][id2] + 1, z[id]);
        }
    }
}