平衡树

gnu pbds 中的 tree：

Luogu-P3369

普通平衡树

1. 插入 $x$ 数
2. 删除 $x$ 数(若有多个相同的数，应只删除一个)
3. 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$ )
4. 查询排名为 $x$ 的数
5. 求 $x$ 的前驱(前驱定义为小于 $x$，且最大的数)
6. 求 $x$ 的后继(后继定义为大于 $x$，且最小的数)

__gnu_pbds::tree 不支持可重复集合，需要自己手动处理。

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>

using namespace std;
using namespace __gnu_pbds;

#define int long long

tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  a;

signed main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int op, x;
    cin >> op >> x;
    if (op == 1) {
      a.insert((x << 20) + i);
    } else if (op == 2) {
      a.erase(a.lower_bound(x << 20));
    } else if (op == 3) {
      cout << a.order_of_key(x << 20) + 1 << endl;
    } else if (op == 4) {
      cout << (*a.find_by_order(x - 1) >> 20) << endl;
    } else if (op == 5) {
      cout << (*(--a.lower_bound(x << 20)) >> 20) << endl;
    } else if (op == 6) {
      cout << (*a.lower_bound((x << 20) + n) >> 20) << endl;
    }
  }
  return 0;
}

std::rope 实现区间翻转：

#pragma GCC optimize(2)
#include <ext/rope>
#include <iostream>

using namespace std;
using namespace __gnu_cxx;

void solve() {
  rope<int> s, rs;
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    s.push_back(i);
    rs.push_back(n - i + 1);
  }
  while (m--) {
    int l, r;
    cin >> l >> r;
    int rl = n - r + 1;
    int rr = n - l + 1;
    --l, --r;
    --rl, --rr;
    auto tmp = s.substr(l, r - l + 1);
    auto rtmp = rs.substr(rl, rr - rl + 1);
    s = s.substr(0, l) + rtmp + s.substr(r + 1, n - r);
    rs = rs.substr(0, rl) + tmp + rs.substr(rr + 1, n - rr);
  }
  for (auto i : s) {
    cout << i << ' ';
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  while (t--) {
    solve();
  }
}