P3369 【模板】普通平衡树

#include <bits/stdc++.h>
#include <functional>
#define ll long long
#define fori(n) for (ll i = 0; i < n; i++)
#define forj(n) for (ll j = 0; j < n; j++)
#define rofi(n) for (ll i = n - 1; i >= 0; i--)
#define rofj(n) for (ll j = n - 1; j >= 0; j--)

// 本题建议使用平衡树、Trie、树状数组，但这是一个线段树实现
// opt 和 x 使用数组是因为要把数据离线下来
const ll N = 1e5 + 4;
ll n, opt[N], x[N];

// 直接用线段树内存是 640 MB，会被卡
// 因此要离散化
// a[i] 存储第 i 个数的排位，b[i] 存储排位为 i 的数的序号
namespace dis {
/* REQUIRED */ ll a[N];
ll a0[N];
ll b[N];
void dis() {
  fori(n) a0[i] = a[i];
  std::sort(a0, a0 + n);
  ll n1 = std::unique(a0, a0 + n) - a0;
  fori(n) a[i] = std::lower_bound(a0, a0 + n1, a[i]) - a0;
  fori(n) b[a[i]] = i;
}
} // namespace dis

// 线段树相关变量还是放在命名空间里面比较好
namespace seg {
/* REQUIRED */ const ll N = 1e5 + 4;
/* REQUIRED */ const ll n = N;
ll a[N << 2];
ll t[N << 2];
inline ll mid(ll l, ll r) { return l + (r - l) / 2; }
inline void pull(ll p) { a[p] = a[p << 1] + a[p << 1 | 1]; }
inline void push(ll l, ll r, ll p) {
  if (r - l != 1) {
    ll m = mid(l, r);
    a[p << 1] += t[p] * (m - l);
    a[p << 1 | 1] += t[p] * (r - m);
    t[p << 1] += t[p];
    t[p << 1 | 1] += t[p];
  }
  t[p] = 0;
}
inline void add(ll lq, ll rq, ll b, ll l = 0, ll r = n, ll p = 1) {
  if (r <= l)
    return;
  push(l, r, p);
  if (lq <= l && rq >= r) {
    a[p] += (r - l) * b;
    t[p] += b;
  } else {
    ll m = mid(l, r);
    if (lq < m)
      add(lq, rq, b, l, m, p << 1);
    if (rq > m)
      add(lq, rq, b, m, r, p << 1 | 1);
    pull(p);
  }
}
inline ll query(ll lq, ll rq, ll l = 0, ll r = n, ll p = 1) {
  if (r <= l)
    return 0;
  ll f = 0;
  push(l, r, p);
  if (lq <= l && rq >= r) {
    f = a[p];
  } else {
    ll m = mid(l, r);
    if (lq < m)
      f += query(lq, rq, l, m, p << 1);
    if (rq > m)
      f += query(lq, rq, m, r, p << 1 | 1);
  }
  return f;
}
} // namespace seg

// 补点二分函数
// 需要一个函数对获得的区间长度判断
// 返回最大的满足条件的数，如果没有则返回 -1，条件应有单调性
// 另一个函数负责二分
ll half(bool (*pred)(ll), ll l, ll r) {
  if (r - l == 1) {
    if (pred(l)) {
      return l;
    } else {
      return -1;
    }
  } else {
    ll m = l + ((r - l) >> 1);
    if (pred(m)) {
      return half(pred, m, r);
    } else {
      return half(pred, l, m);
    }
  }
}

// 定义一些 predicate
// y 用于避免恶心的匿名函数变量捕获
ll y;
bool pred(ll p) { return seg::query(1, p) < y; }

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cin >> n;
  fori(n) std::cin >> opt[i] >> x[i], dis::a[i] = x[i];
  dis::dis();
  fori(n) {
    if (opt[i] == 1 || opt[i] == 2) {
      seg::add(dis::a[i], dis::a[i] + 1, opt[i] == 1 ? 1 : -1);
    } else if (opt[i] == 3) {
      // 查询时从 0 开始，因为有为零的数，最开头没留意到 qwq
      std::cout << seg::query(0, dis::a[i]) + 1 << '\n';
    } else {
      if (opt[i] == 4)
        // 希望定位到前缀 >= 排名时停下，二分结果自动减一
        y = x[i];
      else if (opt[i] == 5)
        // 希望定位到前缀 = 当前位置前缀时停下，二分结果自动减一
        y = seg::query(0, dis::a[i]);
      else
        // 希望定位到前缀 > 当前位置右一格前缀时停下，二分结果自动减一
        y = seg::query(0, dis::a[i] + 1) + 1;
      std::cout << x[dis::b[half(pred, 0, n)]] << '\n';
    }
  }
  return 0;
}