BOJ 9034 - 순위

boj-9034.cpp

#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(),(v).end()

struct seg {
    int n;
    vector<int> t;

    void build(int sz) {
        n = sz;
        t.assign(2 * n, 0);
    }


    // [l, r)
    int query(int l, int r) {
        int ret = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret += t[l++];
            if (r & 1) ret += t[--r];
        }
        return ret;
    }

    void update(int i, int v) {
        for (t[i += n] += v; i > 0; i >>= 1) {
            t[i >> 1] = t[i] + t[i ^ 1];
        }
    }
};

struct query {
    char c;
    int j, k;
};

void solve() {
    int n, q;
    scanf("%d %d", &n, &q);

    vector<int> a(n, 0);
    vector<int> nums(1, 0);
    vector<query> qs;

    for (int i = 0; i < q; ++i) {
        char c;
        int j, k;
        scanf(" %c %d", &c, &j);
        if (c == 'R') {
            scanf("%d", &k);
            a[j - 1] += k;
            nums.push_back(a[j - 1]);
            qs.push_back({c, j - 1, k});
        } else {
            qs.push_back({c, j - 1, 0});
        }
    }
    sort(all(nums));
    nums.erase(unique(all(nums)), nums.end());

    a.assign(n, 0);

    seg t;
    t.build(nums.size());
    t.update(0, n);
    for (auto& q : qs) {
        int idx = lower_bound(all(nums), a[q.j]) - nums.begin();
        if (q.c == 'R') {
            t.update(idx, -1);
            a[q.j] += q.k;
            idx = lower_bound(all(nums), a[q.j]) - nums.begin();
            t.update(idx, +1);
        } else {
            int rank = t.query(idx + 1, nums.size()) + 1;
            printf("%d\n", rank);
        }
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}