平衡树和带插入区间K小值
高速平衡树
除了 Splay 和无旋 Treap 以外的平衡树都是高速平衡树。忘了出处是哪里了，好像是 shadowice1984。
无旋 Treap 的一些写法
随机权值
Treap 的随机权值可以不维护。假如权值是小根堆，那么点 \(p\) 的随机权值可以认为是 \(siz_p\) 个随机数中的最小值。那么我们在比较两个点的随机权值时，使它有 \(\dfrac{siz_p}{siz_p+siz_q}\) 的概率是 \(p\) 的权值小于 \(q\) 的权值，反之亦然。
插入删除只用一次 split/merge
Treap - skip2004 - 博客园
假设随机值是小根堆，对于插入，我们比较随机值，如果随机值比树根小，就把这个树按照插入权值 split 开，然后当成插入节点的两个儿子。不然我们就根据权值比较，进入对应子树继续插入。
删除我们就找到这个节点，把两个儿子 merge 起来，连上去。
如果你学过旋 treap，这个是基本一样的。这样操作还提供了一些额外的性质：
距离叶子期望距离 \(O(1)\)，我们这个节点的期望子树大小 \(O(\log_2 n)\)。
前者保证了我们 split, merge 时候的深度很小，是常数时间，瓶颈在于在上方路径的探查，而这一部分效率非常高。
后者则让我们可以用 treap 实现 平衡树套树，动态标号等功能。
插入的复杂度证明：
对于你要插入的数，你先找到它在 treap 上二分出来的链。我们算每个位置停下的概率乘子树大小的和，就是期望子树大小。
在一个节点停下的概率不好算，但是它不大于在这个节点及上面停下的概率。这个概率就是 \(\frac{1}{1+size}\)，\(size\) 是子树大小。
然后就是 \(\sum size\times \frac{1}{size+1}\)，就是深度，就是 \(O(\log_2 n)\)。
对于离叶子距离，大家感受一下就好，反正是对的。
这样的写法不改变复杂度，但是却实实在在地优化了常数。
区间查询
例如 Treap 维护一个有序序列，查询值域在某个区间内的数有多少个。可以将区间拆成两个前缀的差进行统计。
当然更好的做法是像线段树一样写。我们思考难点在哪里？难点在于我们不知道当前子树代表的区间范围，导致无法判断递归是否需要停止。我们可以回避这件事，在父节点判断询问区间是否完全包含子树区间。从根出发，先向下找到一个子节点 \(p\) 使得 \(l\leq w_p\leq r\)，从这里开始向 \(p\) 的两个儿子分别递归。当然我们不写递归，而是分开两次处理。以 \(p\) 的左儿子为例，从它出发，如果当前点权值 \(\geq l\)，则我们把它和它的右子树全部吃掉，然后跑到左子树；反之跑到右子树。这样就解决了这个问题。
以上的代码汇总
w[pid[p]] 就是节点 \(p\) 的权值，\(w\) 是动态标号，下文介绍。
void insert(int id, int &rt) {pid[++tot] = id, siz[tot] = 1;int *p = &rt; // 防止把根节点改掉而已 while (*p && rng() % (siz[*p] + 1)) ++siz[*p], p = &ch[*p][w[id] > w[pid[*p]]];split(*p, w[id], ch[tot][0], ch[tot][1]);maintain(*p = tot);
}
void erase(int id, int &rt) {int *p = &rt;while (pid[*p] != id) --siz[*p], p = &ch[*p][w[id] > w[pid[*p]]];*p = merge(ch[*p][0], ch[*p][1]);
}
int query(double ql, double qr, int rt) {while (rt && (ql > w[pid[rt]] || w[pid[rt]] > qr)) rt = ch[rt][w[pid[rt]] <= ql];int res = (bool)rt; // 防止根是空的 for (int p = ch[rt][0]; p; ) {if (w[pid[p]] >= ql) res += siz[ch[p][1]] + 1, p = ch[p][0];else p = ch[p][1];}for (int p = ch[rt][1]; p; ) {if (w[pid[p]] <= qr) res += siz[ch[p][0]] + 1, p = ch[p][1];else p = ch[p][0];}return res;
}
替罪羊树
替罪羊树是一种依靠重构操作维持平衡的重量平衡树。它有实现简单，常数小的优点。核心思想是，当 \(\max(siz_{ls[p]}, siz_{rs[p]})\geq \alpha\cdot siz_p\) 时，将整棵子树拍扁重构，也就是取出它的中序遍历，重新建一棵完全二叉树。\(\alpha\) 是一个 \((0.5,1)\) 之间的常数，一般取 \(\alpha=0.7\)。
替罪羊树的删除一般使用懒惰删除，即直接给节点打一个删除标记。当被删除的点的占比 \(\geq \alpha\) 时，也重构整棵子树。
替罪羊树的复杂度是均摊的。
动态标号法
问题是：维护一个序列，支持：在序列第 \(x\) 个元素前插入元素；删除序列第 \(x\) 个元素；查询某两次操作插入的点在序列中的先后关系（要求 \(O(1)\)）。
可以尝试给每个元素分配一个权值 \(w\)。权值是一个外部数组，不存储在平衡树中。假如把 \(m\) 插到 \(l, r\) 之间，则 \(w_m=(w_l+w_r)/2\)。用平衡树维护，把树高控制在 \(O(\log n)\) 以内，权值的精度就可以接受。
平衡树有两种选择：一是替罪羊树，每次重构的时候重新计算权值；二是有旋 Treap，每次旋转的时候重新计算整棵子树的权值，这样的复杂度也是正确的。Treap 一次插入旋转次数期望 \(O(1)\)，旋转的节点的子树大小期望 \(O(\log n)\)。
如何击破 P2617 Dynamic Rankings（带修区间 K-th）
如果我们坚持使用 \(\text{poly}\log\) 的算法，那就必然会出现树套树。问题是选择什么树套什么树。树的类型由两部分组成：一部分是结构，例如这棵树是树状数组、线段树、平衡树之类的（原则上能树状数组就树状数组，否则根据空间需求使用线段树或平衡树）；另一部分是信息，例如这棵树是维护权值的，或者是维护位置的。
第一种方法：位置树套权值树，选择树状数组套线段树。外层树状数组把区间拆成 \(O(\log n)\) 个线段树，然后在这 \(O(\log n)\) 个线段树上同时进行线段树二分。
第二种方法：权值树套位置树，选择树状数组套线段树。外层树状数组进行树状数组二分，内层线段树就做区间查询的工作。
如何击破 P4278 带插入区间K小值
对于插入操作，使用动态标号法解决。这样以后，我们就使用权值树套位置树的区间 k-th 算法（防止潜在的内层树合并问题），选择树状数组套无旋 Treap。时间复杂度 \(O(n\log ^2n)\)，空间复杂度 \(O(n\log n)\)。
\(pid_p\) 存储平衡树节点对应元素的编号，\(w_i\) 存储元素的权值标号。
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
constexpr int N = 70010, V = 70001;
mt19937 rng{141234124};
double w[N];
namespace bbalpha {int ch[N][2], siz[N];void maintain(int p) { siz[p] = siz[ch[p][0]] + siz[ch[p][1]] + 1; }int build(int *fir, int *lst, double l, double r) {if (fir == lst) return 0;assert(fir < lst);auto mid = fir + (lst - fir) / 2;int p = *mid;w[p] = (l + r) / 2;ch[p][0] = build(fir, mid, l, w[p]);ch[p][1] = build(mid + 1, lst, w[p], r);maintain(p);return p;}void rebuild(int &p, double l, double r) {vector<int> vec;auto dfs = [&](auto self, int p) -> void {if (!p) return ;self(self, ch[p][0]);vec.push_back(p);self(self, ch[p][1]);};dfs(dfs, p);p = build(vec.data(), vec.data() + vec.size(), l, r);}void insert(int x, int k, int &p, double l, double r) {if (!p) return assert(!k), w[p = x] = (l + r) / 2, siz[p] = 1, void();if (siz[ch[p][0]] + 1 <= k) insert(x, k - siz[ch[p][0]] - 1, ch[p][1], w[p], r);else insert(x, k, ch[p][0], l, w[p]);maintain(p);if (max(siz[ch[p][0]], siz[ch[p][1]]) >= 0.7 * siz[p]) rebuild(p, l, r);}int query(int k, int p) {assert(p);if (k == siz[ch[p][0]] + 1) return p;if (siz[ch[p][0]] + 1 < k) return query(k - siz[ch[p][0]] - 1, ch[p][1]);return query(k, ch[p][0]);}
};
namespace treap {int rt[N], ch[N * 80][2], siz[N * 80], pid[N * 80], tot;void maintain(int p) {siz[p] = siz[ch[p][0]] + siz[ch[p][1]] + 1;}int merge(int p, int q) {if (!p || !q) return p + q;if (rng() % (siz[p] + siz[q]) < siz[p]) {ch[p][1] = merge(ch[p][1], q);maintain(p);return p;} else {ch[q][0] = merge(p, ch[q][0]);maintain(q);return q;}}void split(int p, double k, int &x, int &y) {if (!p) return x = y = 0, void();if (w[pid[p]] <= k) x = p, split(ch[p][1], k, ch[p][1], y);else y = p, split(ch[p][0], k, x, ch[p][0]);maintain(p);}void split2(int p, double k, int &x, int &y) {if (!p) return x = y = 0, void();if (w[pid[p]] < k) x = p, split2(ch[p][1], k, ch[p][1], y);else y = p, split2(ch[p][0], k, x, ch[p][0]);maintain(p);}void insert(int id, int &rt) {pid[++tot] = id, siz[tot] = 1;int *p = &rt; // 防止把根节点改掉而已 while (*p && rng() % (siz[*p] + 1)) ++siz[*p], p = &ch[*p][w[id] > w[pid[*p]]];split(*p, w[id], ch[tot][0], ch[tot][1]);maintain(*p = tot);}void erase(int id, int &rt) {int *p = &rt;while (pid[*p] != id) --siz[*p], p = &ch[*p][w[id] > w[pid[*p]]];*p = merge(ch[*p][0], ch[*p][1]);}int query(double ql, double qr, int rt) {while (rt && (ql > w[pid[rt]] || w[pid[rt]] > qr)) rt = ch[rt][w[pid[rt]] <= ql];int res = (bool)rt; // 防止根是空的 for (int p = ch[rt][0]; p; ) {if (w[pid[p]] >= ql) res += siz[ch[p][1]] + 1, p = ch[p][0];else p = ch[p][1];}for (int p = ch[rt][1]; p; ) {if (w[pid[p]] <= qr) res += siz[ch[p][0]] + 1, p = ch[p][1];else p = ch[p][0];}return res;}
};
int n;
void insert(int x, int y) {debug("insert(%d, %d) [w = %.3lf]\n", x, y, w[x]);for (int p = y; p <= V; p += p & -p) treap::insert(x, treap::rt[p]);
}
void erase(int x, int y) {debug("erase(%d, %d) [w = %.3lf]\n", x, y, w[x]);for (int p = y; p <= V; p += p & -p) treap::erase(x, treap::rt[p]);
}
int query(int l, int r, int k) {debug("query(%d, %d, %d) [w = [%.3lf, %.3lf]]\n", l, r, k, w[l], w[r]);int p = 0;for (int j = 17; j >= 0; j--) {int q = p | 1 << j, res;if (q > V) continue;if (q <= V && (res = treap::query(w[l], w[r], treap::rt[q])) < k) k -= res, p = q;}return p;
}
int main() {
#ifndef LOCALcin.tie(nullptr)->sync_with_stdio(false);
#endifcin >> n;vector<int> vec(n);iota(vec.begin(), vec.end(), 1);int rt = bbalpha::build(vec.data(), vec.data() + vec.size(), 0, 1e9);static int val[N];for (int i = 1; i <= n; i++) cin >> val[i], insert(i, ++val[i]);int q, lstans = 0;cin >> q;while (q--) {char op;int x, y, k;cin >> op >> x >> y;x ^= lstans, y ^= lstans;if (op == 'Q') cin >> k, k ^= lstans, cout << (lstans = query(bbalpha::query(x, rt), bbalpha::query(y, rt), k)) << endl;else if (op == 'M') x = bbalpha::query(x, rt), erase(x, val[x]), insert(x, val[x] = ++y);else bbalpha::insert(++n, --x, rt, 0, 1e9), insert(n, val[n] = ++y);}return 0;
}