【luogu P4278】【ybt金牌导航4-5-2】带插入区间K小值（树套树做法）

带插入区间K小值

题目链接：luogu P4278 / ybt金牌导航4-5-2

题目大意

要你维护待插入和修改的区间 k 小在线的查询。

思路

正解是块状链表+值域分块，但是我是在替罪羊树专题里面看到这道题了，就用的是树套树。
然后写完之后看了看正解的做法，懒得写的但是代码的下面会讲讲大概做法。

提前说好，我的代码只能过 luogu 的数据（还要开 O2），因为树套树的复杂度确实非常的不优，我也是卡了很久才卡过去的。
ybt 上直接卡 1s，怎么搞都搞不过去。

昨晚
我：阿巴阿巴，到替罪羊的例题了呀，然后看题。
看到求区间第 k 小——树状数组套线段树！
然后要修改——还是可以！
然后要插入，emmmm。
然后想了想可以把外面的改成平衡树，那理论上就可以实现插入了。
然后发现如果要旋转我们不知道要怎么搞才能缩小时间，然后就想到了无旋 Treap 和替罪羊。
然后瞄了一样专题是替罪羊，而且想到无旋 Treap 拆开合并也耗时间，那就用替罪羊吧。

然后，看着想出来的奇妙鬼玩意，我停止了思考。
于是我翻开了题解，然后我看了一个晚上才把题解的代码看懂。
*龙门粗口*

然后我码一开始的代码就码了一个上午。
*龙门粗口*
然后显而易见的是我卡常卡了一个下午。
*龙门粗口*

然后大概是你替罪羊的每个点对应数组的集合都开一个线段树。
那容易看出数组的一个数会影响一条链，一条替罪羊上的链，也就是很多个线段树。
我们每次要把影响的链找出来，枚举其中的点，然后对线段树进行操作。
而容易想到我们会有合并线段树的操作，其实并不是什么奇怪的玩意儿，就是把它们各个位置的权值相加罢了。

然后你可以看到你重构会删掉线段树，那我们还是用一个栈，把可以用的位置放进去。
每次要开新点就往里面拿，删线段树的时候就遍历你要删的点，除了清空值还把他们放进栈中。
（这样就不会爆空间了）

然后卡常就是调调平衡因子，重构的时候出了判断平衡还要让深度小于一个值才重构。
（不然你一直重构也浪费时间，而且可能会一条链上的点轮流重构，看着就不优）
然后这个你可以是 log(数的个数) / 零点几。
然后快读快输，register，再开个 O2 什么的就过去了。

具体实现可以看看代码。

代码

#include<cmath>
#include<cstdio>
#define alph (0.88)
#define rr register
//#define logalph (log(4.0) - log(3.0))
#define logalph (0.15)using namespace std;int n, a[70001], Q, lastans, x, y, z, logg[70001];
char op;struct xianduanshu {int ls, rs, sum;
}tree[20000010];
struct tizuiyang {int ls, rs, sz, rt;//rt 记录的是替罪羊树啥这个点对应的线段树的根节点是哪个
}tr[70001];
int place_xdx[20000010], root;
int dfn[70001], Val[70001];
int maxdeg;int read() {rr int re = 0;char c = getchar();while (c < '0' || c > '9') c = getchar();while (c >= '0' && c <= '9') {re = (re << 3) + (re << 1) + c - '0';c = getchar();}return re;
}void write(rr int now) {if (now > 9) write(now / 10);putchar(now % 10 + '0');
}void xianduanshu_clear(rr int now) {tree[now] = (xianduanshu){0, 0, 0};
}void xianduanshu_throw(rr int &now) {//删掉线段树上的点，即把它们的位置标记为可以用place_xdx[++place_xdx[0]] = now;if (tree[now].ls) xianduanshu_throw(tree[now].ls);if (tree[now].rs) xianduanshu_throw(tree[now].rs);xianduanshu_clear(now);now = 0;
}int xianduanshu_newpoint() {//线段树开新点rr int re = place_xdx[place_xdx[0]--];xianduanshu_clear(re);return re;
}void xianduanshu_make_tree(rr int &root, rr int x) {//建一个点对应的线段树root = xianduanshu_newpoint();tree[root].sum = 1;rr int now = root, l = 0, r = 70000;while (l < r) {int mid = (l + r) >> 1;if (x <= mid) {tree[now].ls = xianduanshu_newpoint();now = tree[now].ls;r = mid;}else {tree[now].rs = xianduanshu_newpoint();now = tree[now].rs; l = mid + 1;}tree[now].sum++;}
}void xianduanshu_insert(rr int &now, rr int l, rr int r, rr int pl, rr int val) {//在线段树中插入一个点if (!now) now = xianduanshu_newpoint();tree[now].sum += val;if (l == r) return ;rr int mid = (l + r) >> 1;if (pl <= mid) xianduanshu_insert(tree[now].ls, l, mid, pl, val);else xianduanshu_insert(tree[now].rs, mid + 1, r, pl, val);
}void xianduanshu_merge(rr int &x, rr int y) {//把两个线段树的值合并到左边的线段树中if (!y) return ; if (!x) x = xianduanshu_newpoint();tree[x].sum += tree[y].sum;//其实就是把权值加过去xianduanshu_merge(tree[x].ls, tree[y].ls);xianduanshu_merge(tree[x].rs, tree[y].rs);
}int tizuiyang_build(rr int l, rr int r) {//建替罪羊树rr int mid = (l + r) >> 1;rr int now = dfn[mid];xianduanshu_make_tree(tr[now].rt, a[now]);//对于每个点都要建一个线段树if (l < mid) tr[now].ls = tizuiyang_build(l, mid - 1);if (mid < r) tr[now].rs = tizuiyang_build(mid + 1, r);tr[now].sz = tr[tr[now].ls].sz + tr[tr[now].rs].sz + 1;//原本的合并节点信息就变成了合并线段树xianduanshu_merge(tr[now].rt, tr[tr[now].ls].rt);xianduanshu_merge(tr[now].rt, tr[tr[now].rs].rt);return now;
}void tizuiyang_get_dfn_all(rr int now) {//将这个替罪羊树这个点的子树提取出来if (tr[now].ls) tizuiyang_get_dfn_all(tr[now].ls);dfn[++dfn[0]] = now;if (tr[now].rs) tizuiyang_get_dfn_all(tr[now].rs);
}void tizuiyang_get_dfn_part(rr int now, rr int rnk) {//提取替罪羊树从起点到第 k 小的点的路径dfn[++dfn[0]] = now;if (tr[tr[now].ls].sz >= rnk) tizuiyang_get_dfn_part(tr[now].ls, rnk);else if (tr[tr[now].ls].sz + 1 == rnk) return ;else tizuiyang_get_dfn_part(tr[now].rs, rnk - tr[tr[now].ls].sz - 1);
}void tizuiyang_get_inside(rr int now, rr int l, rr int r, rr int L, rr int R) {//将这段区间内的点找出来if (L <= l && r <= R) {//可以直接确定一个平衡树内的区间都是在询问区间里面的dfn[++dfn[0]] = tr[now].rt;return ;}rr int mid = l + tr[tr[now].ls].sz;if (L < mid && tr[now].ls) tizuiyang_get_inside(tr[now].ls, l, mid - 1, L, R);if (L <= mid && mid <= R) Val[++Val[0]] = a[now];if (mid < R && tr[now].rs) tizuiyang_get_inside(tr[now].rs, mid + 1, r, L, R);
}int tizuiyang_Query(rr int l, rr int r, rr int rnk) {//询问区间第 k 小dfn[0] = Val[0] = 0;tizuiyang_get_inside(root, 1, n, l, r);//先找到所有这段区间的替罪羊树（和点）l = 0;r = 70000;while (l < r) {//二分数的大小（这个时候会同时在线段树上跑）rr int mid = (l + r) >> 1;rr int number = 0;for (rr int i = 1; i <= dfn[0]; i++)//枚举每个替罪羊树上的点代表的线段树，找它有多少个小于等于它的数number += tree[tree[dfn[i]].ls].sum;for (rr int i = 1; i <= Val[0]; i++)//看那些点是否满足条件if (l <= Val[i] && Val[i] <= mid) number++;if (number < rnk) {//根据个数确定二分的答案的位置rnk -= number;l = mid + 1;for (int i = 1; i <= dfn[0]; i++)//在这些线段树上跑，下面也一样dfn[i] = tree[dfn[i]].rs;}else {r = mid;for (int i = 1; i <= dfn[0]; i++)dfn[i] = tree[dfn[i]].ls;}}return l;
}void tizuiyang_change(rr int pl, rr int val) {//将一个数修改乘另一个数dfn[0] = 0;tizuiyang_get_dfn_part(root, pl);//提取起点到这个数在替罪羊树上经过的点rr int bef = a[dfn[dfn[0]]];for (rr int i = 1; i <= dfn[0]; i++) {xianduanshu_insert(tr[dfn[i]].rt, 0, 70000, bef, -1);//把原来的数从这个线段树上消掉xianduanshu_insert(tr[dfn[i]].rt, 0, 70000, val, 1);//把新的数放进这个线段树里面}a[dfn[dfn[0]]] = val;//改值
}int tizuiyang_rebuild(rr int now) {//替罪羊树的重新构造dfn[0] = 0;tizuiyang_get_dfn_all(now);//把整个子树找到（拍扁）for (rr int i = 1; i <= dfn[0]; i++) {//清空rr int x = dfn[i];xianduanshu_throw(tr[x].rt);tr[x].ls = tr[x].rs = tr[x].sz = 0;}return tizuiyang_build(1, dfn[0]);//重新建
}bool tizuiyang_insert_num(rr int &now, rr int rnk, rr int pl, rr int deg) {//在平衡树中插入点if (!now) {now = pl;tr[now].sz++;xianduanshu_make_tree(tr[now].rt, a[now]);return deg <= maxdeg;//这里是设定了一个深度，小于这个深度再重构}tr[now].sz++;xianduanshu_insert(tr[now].rt, 0, 70000, a[pl], 1);bool pd = 0;if (rnk <= tr[tr[now].ls].sz + 1) pd = tizuiyang_insert_num(tr[now].ls, rnk, pl, deg + 1);else pd = tizuiyang_insert_num(tr[now].rs, rnk - tr[tr[now].ls].sz - 1, pl, deg + 1);//判断&重构if (pd && tr[now].sz * alph < tr[tr[now].ls].sz || tr[now].sz * alph < tr[tr[now].rs].sz) {now = tizuiyang_rebuild(now);return 0;}return pd; 
}void tizuiyang_insert(rr int rnk, rr int val) {a[++n] = val;//把它放进树里面maxdeg = logg[n] / logalph;//根据你的函数推出重构的深度不要超过多少tizuiyang_insert_num(root, rnk, n, 0);//把 n 这个位置的数放进替罪羊的 rank 位置
}int main() {
//	freopen("read.txt", "r", stdin);
//	freopen("write.txt", "w", stdout);n = read();for (rr int i = 1; i <= n; i++) {a[i] = read();dfn[i] = i;}for (rr int i = n; i <= 70000; i++)logg[i] = log(1.0 * i);for (rr int i = 20000000 - 1; i >= 1; i--)//一开始所有的空间都能用place_xdx[++place_xdx[0]] = i;root = tizuiyang_build(1, n);Q = read();while (Q--) {op = getchar();while (op != 'Q' && op != 'M' && op != 'I') op = getchar();if (op == 'Q') {x = read() ^ lastans; y = read() ^ lastans; z = read() ^ lastans;lastans = tizuiyang_Query(x, y, z);write(lastans);putchar('\n');}else if (op == 'M') {x = read() ^ lastans; z = read() ^ lastans;tizuiyang_change(x, z);}else if (op == 'I') {x = read() ^ lastans; z = read() ^ lastans;tizuiyang_insert(x, z);}}return 0;
}

正解应该怎么做

首先我们一步一步想，没有插入，也没有修改，就连区间都是固定的要怎么做。
不要骂是 SB 题，用分块的做法。
容易想到分成 $\sqrt{n}$ 个块，然后 $O(n)$ 记录每个块中有多少个数，$O(n)$ 记录这个数在数组中出现次数。
先根据块中个数确定你要的数在哪个块，然后根据数在数组中出现次数找到在块的哪个位置。

然后接着我们看吧区间搞成不固定。
然后考虑还是同样方法，然后记录的变成二维，记录前 $i$ 块值域是 $j$ 块中有多少个数。（$O(n\sqrt{n})$）
记录前 $i$ 块 $j$ 出现过多少次（前缀和搞搞 $O(n\sqrt{n})$）
然后我们考虑询问，如果 $x,y$ 在同一块，那就是跟区间固定一样的做法。
如果不一样，我们就先把散的处理的，再处理整块的。（整块可以用前缀和求）

然后再加单点修改。
那就只用修改它所在块的这两个值，复杂度完全没有问题。

然后就只剩插入了。
你考虑插入就插入它左边所在块里面，就当它这个数放进了这个块里面。
但是你会发现放多了它就不优了。
那你考虑多的拆开成两个，由于级别是 $\sqrt{n}$，也可以很好解决。
但你遍历块的顺序。。。容易想到你是按着从头到尾的顺序一个一个摸过去的，那我们完全可以搞一个链表。

然后做法就出来了，这个看起来实现就比我用的树套树好写一万倍，但我实在是不想写了。

*龙门粗口*
（什么写树套树写到心态炸裂）