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]); } } }
