Codeforces Round #348 Div2 E: Little Artem and Time Machine
解法
各xについて独立に考えることができる。各xについてtを座標圧縮して、Fenwick Tree を使って管理する。
コード
#include <bits/stdc++.h> using namespace std; template <typename T> void uniq(vector<T> &v) { v.erase(unique(v.begin(), v.end()), v.end()); } template <typename T> class FenwickTree { public: int N; vector<T> dat; public: FenwickTree(int N) : N(N + 1) { dat.assign(N + 1, 0); } void add(int k, T val) { for (int x = k; x < N; x |= x + 1) { dat[x] += val; } } // [0, k) T sum(int k) { if (k >= N) k = N - 1; T ret = 0; for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) { ret += dat[x]; } return ret; } // [l, r) T sum(int l, int r) { return sum(r) - sum(l); } T get(int k) { assert(0 <= k && k < N); return sum(k + 1) - sum(k); } int lower_bound(int w) { if (w <= 0) return -1; int x = 0; int k = 1; while (k * 2 <= N) k *= 2; for (; k > 0; k /= 2) { if (x + k <= N && dat[x + k - 1] < w) { w -= dat[x + k - 1]; x += k; } } return x; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; scanf("%d", &N); vector<int> a(N), t(N), x(N); for (int i = 0; i < N; ++i) scanf("%d %d %d", &a[i], &t[i], &x[i]); vector<int> xx = x; sort(xx.begin(), xx.end()); uniq(xx); for (auto &xi : x) xi = lower_bound(xx.begin(), xx.end(), xi) - xx.begin(); vector<vector<int>> t_buckets(*max_element(x.begin(), x.end()) + 1); for (int i = 0; i < N; ++i) t_buckets[x[i]].push_back(t[i]); for (auto &bucket : t_buckets) { sort(bucket.begin(), bucket.end()); uniq(bucket); } for (int i = 0; i < N; ++i) { auto &bucket = t_buckets[x[i]]; t[i] = lower_bound(bucket.begin(), bucket.end(), t[i]) - bucket.begin(); } vector<FenwickTree<int>> fenwicks; for (auto &bucket : t_buckets) fenwicks.push_back(FenwickTree<int>(bucket.size())); for (int i = 0; i < N; ++i) { if (a[i] == 1) { fenwicks[x[i]].add(t[i], 1); } else if (a[i] == 2) { fenwicks[x[i]].add(t[i], -1); } else { printf("%d\n", fenwicks[x[i]].sum(t[i])); } } }