哎，今天立了个 flag，那就先学一个树套树吧。
线段树套平衡树
- 前置芝士：线段树、平衡树、二分答案
顾名思义，线段树套平衡树是给线段树的每个节点都建一颗平衡树。我们先不考虑空间复杂度的问题。
那么它一般用来解决什么问题呢？首先，线段树一般是用来维护序列的区间操作的，而平衡树一般针对于非区间操作的复杂问题。所以当二者结合起来，相当于我们要维护一个序列，并且可以解决区间操作的复杂问题，该怎么办呢？
换言之，我们需要用线段树维护区间操作，但区间内需要维护的东西又是需要平衡树来解决的，这时候我们就需要使用线段树套平衡树来解决。
如果有读者不理解复杂问题，可以参考以下的例子：对于序列第 \(k\) 小问题，我们无法使用普通的线段树操作。
好了，我们从一到模板题入手。
我们需要实现一种数据结构，来支持：
-
单点修改
-
查询区间第 \(k\) 小
-
查询 \(p\) 在区间里的排名
-
查询区间内的前驱和后继
这道题中，如果把“区间”二字去掉，就成了普通的平衡树问题。所以这道题是需要我们解决区间操作的复杂问题，考虑使用线段树套平衡树。
由于外层是线段树，我们按照线段树的方式来讨论。平衡树建议使用 Fhq-Treap。
1. 建树
我们每次对于表示区间 \([l, r]\) 的线段树节点 \(u\) 建树时，把 \(a_i, i \in [l, r]\) 插入到这个节点对应的平衡树中。
这里面的平衡树建议用一个结构体封装。至于空间复杂度的问题，我们考虑建一个平衡树森林，然后对于每颗平衡树，只需要记录它的根即可。
平衡树代码:
平衡树
int n, ts, a[N];
struct node{
int ls, rs;
int ky, vl, sz;
}t[M];
struct treap{
int rt;
void pushup(int u) {
t[u].sz = t[t[u].ls].sz + t[t[u].rs].sz + 1;
}
void mknode(int x) {
++ts;
t[ts] = (node){0, 0, x, rand(), 1};
}
void split(int u, int x, int &l, int &r) {
if (!u) {
l = r = 0;
return ;
}
if (t[u].ky <= x) {
l = u;
split(t[u].rs, x, t[u].rs, r);
} else {
r = u;
split(t[u].ls, x, l, t[u].ls);
}
pushup(u);
}
int merge(int l, int r) {
if (!l || !r) return l + r;
if (t[l].vl < t[r].vl) {
t[r].ls = merge(l, t[r].ls);
pushup(r);
return r;
} else {
t[l].rs = merge(t[l].rs, r);
pushup(l);
return l;
}
}
void ins(int x) {
int l, r;
split(rt, x, l, r);
mknode(x);
rt = merge(l, merge(ts, r));
}
void del(int x) {
int a, b, c;
split(rt, x - 1, a, b);
split(b, x, b, c);
b = merge(t[b].ls, t[b].rs);
rt = merge(a, merge(b, c));
}
int grk(int x) {
int l, r, res;
split(rt, x - 1, l, r);
res = t[l].sz + 1;
rt = merge(l, r);
return res;
}
int kth(int u, int k) {
if (k == t[t[u].ls].sz + 1) return u;
if (k <= t[t[u].ls].sz) return kth(t[u].ls, k);
return kth(t[u].rs, k - t[t[u].ls].sz - 1);
}
int pre(int x) {
int l, r, res;
split(rt, x - 1, l, r);
if (!t[l].sz) res = -I;
else res = t[kth(l, t[l].sz)].ky;
rt = merge(l, r);
return res;
}
int suc(int x) {
int l, r, res;
split(rt, x, l, r);
if (!t[r].sz) res = I;
else res = t[kth(r, 1)].ky;
rt = merge(l, r);
return res;
}
void build(int l, int r) {
for (int i = l; i <= r; i++) {
ins(a[i]);
}
}
}ft[N << 2];