読者です 読者をやめる 読者になる 読者になる

Codeforces Round #348 Div2 E: Little Artem and Time Machine

Codeforces 競技プログラミング

解法

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