白駿2243号:キャンディボックス

11797 ワード
Segment Tree ps Binary Search cpp テキストリンク

キャンディボックス


白駿2243号:キャンディボックス

アイデア


各セグメントのキャンディボックスを貯蔵する.
2位のおいしいキャンディを探しているときは、セグメントツリーでバイナリ検索ができます!
ルートノードから、左ノードが格納されている場合とrankより大きい場合は左、rankより大きい場合は右.このとき、次のサブツリーに同じルールを適用するために、rankからleft nodeに格納されている合計を減算します.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

int N;
const int MAX = 1000000;
vector<int> tree(4*MAX, 0);

void update(int start, int end, int idx, int diff, int node) {
    if (idx < start || end < idx) return;
    tree[node] += diff;
    if (start == end) return;
    update(start, (start+end)/2, idx, diff, node*2);
    update((start+end)/2+1 ,end, idx, diff, node*2+1);
}

int query(int start, int end, int rank, int node) {
    if (start == end) return start;
    if (tree[node*2] < rank) {
        return query((start+end)/2+1, end, rank-tree[node*2], node*2+1);
    }
    else {
        return query(start, (start+end)/2, rank, node*2);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int a, b, c;
        cin >> a;
        if (a == 1) {
            cin >> b;
            int candy = query(0, MAX-1, b, 1);
            cout << candy+1 << '\n';
            update(0, MAX-1, candy, -1, 1);
        }
        else if (a == 2) {
            cin >> b >> c;
            update(0, MAX-1, b-1, c, 1);
        }
    }
    return 0;
}

おしゃべり


インデックスはちょっと下手で、(start+end)/2+1でいいのですが、+1がなくてうろうろしていて、
これからのスタートを混同しないためには必ず0から
[BOJ]206:壁を破って移動する
自己署名による証明書の生成