AtCoder Regular Contest 033 C: データ構造

問題

C: データ構造 - AtCoder Regular Contest 033 | AtCoder

解法

@kenkoooo BITには二分探索というテクがあるそうです(受け売りhttps://t.co/VM8Y0DxGUz

— CodeVS本戦通過ラインの境界 (@btk15049) 2016, 3月 8

lower_bound() 搭載 Binary Indexed Tree (BIT)

コード

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

template <typename T>
class FenwickTree {
 public:
  int N;
  vector<T> dat;

 public:
  FenwickTree(int N) : N(N) { dat.assign(N, 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 Q;
  cin >> Q;

  FenwickTree<int> bit(200010);
  while (Q--) {
    int T, X;
    cin >> T >> X;
    if (T == 1) {
      bit.add(X, 1);
    } else {
      int z = bit.lower_bound(X);
      cout << z << endl;
      bit.add(z, -1);
    }
  }
}