Splay简易教程
tiger0132
2018-08-02 21:45:56
# 一些锅的澄清
@[March_H](https://www.luogu.org/space/show?uid=92770) 真是一位预言家 dalao……
## 关于 find
find 原来的定义有锅，更新为：
当原数存在时，find 会返回原数。否则 find 会返回**当前数的前驱或后继**。
**在 pre 和 succ 中，find 得到的根可以当做原数使用。**
## 关于 rank
rank 在原数不存在的时候会出锅。
当 find 得到前驱的时候，根节点的 cnt 也是答案的一部分，必须加上。
rank 操作更新如下：
```cpp
find(x);
if (val[root] >= x) printf("%d\n", size[ch[root][0]] - 1);
else printf("%d\n", size[ch[root][0]] + cnt[root] - 1);
```
### **Upd 2018.12.23**
rank 操作中 `-1` 的原因是初始化时 insert 了极小值。如果不 insert 最小值，需要删掉 `-1`。
# 简介
二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
1. 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
2. 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
3. 左、右子树也分别为二叉排序树
同样的序列，因为排序不同，可能会生成不同的二叉排序树，查找效率性对就不一定了。如果是二叉排序树退化成一条链，效率就很低。
伸展树（Splay）是一种平衡二叉树，即优化后的二叉查找树。伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)，使得提升效率。
**⚠️多图预警**
图片均为原创，协议为CC0，***尽量***保留原地址。
~~劼司机的图片风格太赞啦~~
# 前置技能
线段树。
# 变量定义
`N`：常量，节点个数。
`ch[N][2]`：二维数组，`ch[x][0]`代表$x$的左儿子，`ch[x][1]`代表$x$的右儿子。
`val[N]`：一维数组，`val[x]`代表$x$存储的值。
`cnt[N]`：一维数组，`cnt[x]`代表$x$存储的重复权值的个数。
`par[N]`：一维数组，`par[x]`代表$x$的父节点。
`size[N]`：一维数组，`size[x]`代表$x$子树下的储存的权值数（包括重复权值）。
# 各种操作
## chk操作
辅助操作，查询一个节点位于其父节点的方向。
```cpp
int chk(int x) {
return ch[par[x]][1] == x;
}
```
## pushup操作
辅助操作，更新size数组的值。
```cpp
void pushup(int x) {
size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
}
```
## 旋转(rotate)
Splay使用旋转保持平衡。所以旋转是最重要的操作，也是最核心的操作。
**Splay旋转后，中序遍历和Splay的合法性不变。**
比如最开始的树是这样子的：
现在我们想把$2$号点搞到$4$号点的位置。
那么$2$下面的子树就有$1,3,4,5$。一种比较优秀的玩法是这样的：
那么我们可以考虑这么操作：
1. 先把$4\rightarrow2$的边改成$4\rightarrow3$。
2. 再把$6\rightarrow4$的边改成$6\rightarrow2$。
3. 最后把$2\rightarrow3$的边改成$2\rightarrow4$。
### 第一次连边
### 第二次连边
### 第三次连边
### 连边前(原图)
旋转操作有四种。自行模拟后发现：
旋转后，父节点会将连向需旋转的该子节点的方向的边连向该子节点位于其父节点方向的反方向的节点。
令`x = 该节点, y = par[x], k = chk(x), w = ch[x][k^1]`，则`ch[y][k] = w; par[w] = y;`
旋转后，爷爷节点会将连向父节点的边连向需旋转的该节点。
`ch[z][chk(y)] = x; par[x] = z;`
旋转后，需旋转的该节点会将连向该子节点位于其父节点方向的反方向的子节点的边连向其父节点。
`ch[x][k^1] = y; par[y] = x;`
综合一下，得到下列代码(~~可见自然语言是多么的无力~~)：
```cpp
void rotate(int x) {
int y = par[x], z = par[y], k = chk(x), w = ch[x][k^1];
ch[y][k] = w; par[w] = y;
ch[z][chk(y)] = x; par[x] = z;
ch[x][k^1] = y; par[y] = x;
pushup(y); pushup(x);
}
```
## 伸展(splay)
将一个节点一路rotate到指定节点的儿子。
注意，如果该节点、该父节点和该爷爷节点「三点一线」，那么应该先旋转父节点。
此处进行的操作是将$3$ splay到根节点。
### 原图
### 旋转父节点后
### 旋转自身后
剩下的情况~~自行模拟~~没图片了。
并且注意处理爷爷节点已经是目标的情况。
```cpp
void splay(int x, int goal = 0) {
while (par[x] != goal) {
int y = par[x], z = par[y];
if (z != goal) {
if (chk(x) == chk(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
if (!goal) root = x;
}
```
## find操作
辅助操作，将最大的小于等于$x$的数所在的节点splay到根。
```cpp
void find(int x) {
if (!root) return;
int cur = root;
while (ch[cur][x > val[cur]] && x != val[cur]) {
cur = ch[cur][x > val[cur]];
}
splay(cur);
}
```
## 插入(insert)
从根节点开始，一路搜索下去。如果节点存在则直接自增cnt的值。否则新建节点并与父节点连边。
因为新建节点时可能会拉出一条链，所以新建节点后需要将该节点splay到根节点。沿途的rotate操作可以使平衡树恢复平衡。
```cpp
void insert(int x) {
int cur = root, p = 0;
while (cur && val[cur] != x) {
p = cur;
cur = ch[cur][x > val[cur]];
}
if (cur) {
cnt[cur]++;
} else {
cur = ++ncnt;
if (p) ch[p][x > val[p]] = cur;
ch[cur][0] = ch[cur][1] = 0;
val[cur] = x; par[cur] = p;
cnt[cur] = size[cur] = 1;
}
splay(cur);
}
```
## 查询k大(kth)
从根节点开始，一路搜索下去。每次判断要走向哪个子树。注意考虑重复权值。
```cpp
int kth(int k) {
int cur = root;
while (1) {
if (ch[cur][0] && k <= size[ch[cur][0]]) {
cur = ch[cur][0];
} else if (k > size[ch[cur][0]] + cnt[cur]) {
k -= size[ch[cur][0]] + cnt[cur];
cur = ch[cur][1];
} else {
splay(cur);
return cur;
}
}
}
```
## 查询rank(rank)
并不需要专门写操作。将该节点find到根后返回左子树的权值数即可。
```cpp
find(x);
printf("%d\n", size[ch[root][0]]);
```
## 前驱(pre)
将该节点find到根后返回左子树最右边的节点即可。
```cpp
int pre(int x) {
find(x);
if (val[root] < x) return root;
int cur = ch[root][0];
while (ch[cur][1]) {
cur = ch[cur][1];
}
splay(cur);
return cur;
}
```
## 后继(succ)
同理，返回右子树最左边的节点即可。
```cpp
int succ(int x) {
find(x);
if (val[root] > x) return root;
int cur = ch[root][1];
while (ch[cur][0]) {
cur = ch[cur][0];
}
splay(cur);
return cur;
}
```
## 删除(remove)
显然，任何一个数的前驱和后继之间只有它自身。
令该点的前驱为$last$，后继为$next$。
那么可以考虑把前驱splay到根，后继splay到前驱的右儿子，那么后继的左儿子就是要删除的点。
**注意，请将图上的 next 和 last 的位置替换。**
最后判特判权值数大于$1$的情况即可。
```cpp
void remove(int x) {
int last = pre(x), next = succ(x);
splay(last); splay(next, last);
int del = ch[next][0];
if (cnt[del] > 1) {
cnt[del]--;
splay(del);
}
else ch[next][0] = 0;
pushup(next), pushup(x);
}
```
## 区间反转
考虑线段树维护区间标记的方法，将其移植到Splay即可。
打标记时，将$l-1$和$r+1$分别旋转到根节点和根节点右儿子处，那么$r+1$的左子树即是区间$[l,r]$。在其根处打上标记然后在查询$k$大和输出中序遍历时下传标记即可。
```cpp
void pushdown(int x) {
if (rev[x]) {
swap(ch[x][0], ch[x][1]);
rev[ch[x][0]] ^= 1;
rev[ch[x][1]] ^= 1;
rev[x] = 0;
}
}
int kth(int k) {
int cur = root;
while (1) {
pushdown(cur);
if (ch[cur][0] && k <= size[ch[cur][0]]) {
cur = ch[cur][0];
} else if (k > size[ch[cur][0]] + cnt[cur]) {
k -= size[ch[cur][0]] + cnt[cur];
cur = ch[cur][1];
} else {
splay(cur);
return cur;
}
}
}
void reverse(int l, int r) {
int x = kth(l), y = kth(r+2);
splay(x); splay(y, x);
rev[ch[y][0]] ^= 1;
}
void output(int x) {
pushdown(x);
if (ch[x][0]) output(ch[x][0]);
if (val[x] && val[x] <= n) printf("%d ", val[x]);
if (ch[x][1]) output(ch[x][1]);
}
```
> // 这张图有点小
## 区间打标记
平衡树像线段树一样，可以打标记。但是有一个不同点，就是**平衡树的每个节点都有权值**。所以更新标记时和线段树不一样，要考虑自身节点的权值。
因为Splay可以直接提取指定区间，所以Splay的区间操作在某些意义上~~比线段树还好写~~。
# 例题 [P2042 维护数列](https://www.luogu.org/problemnew/show/P2042)
策爷：“splay/块状链表的自虐题。”
看到插入、删除、反转就很容易想到~~fhq-treap~~Splay。
## 简化版问题
如果只考虑修改、求和、求最大子段和，就可以直接用线段树解决。
考虑维护`la[N]`、`ra[N]`、`gss[N]`、`sum[N]`、`upd[N]`，分别代表最大前缀和、最大后缀和、最大子段和、区间和和修改标记。
初始化`la`、`ra`时，在选与不选之间取max即可。`gss`则初始化为叶子的值即可。
`la[x] = ra[x] = max(0, sum[x]); gss[x] = sum[x];`
考虑如何维护`la`、`ra`、`gss`和`sum`。
```cpp
la[x] = max(la[l], sum[l] + la[r]);
ra[x] = max(ra[r], sum[r] + ra[l]);
gss[x] = max(ra[l] + la[r], max(gss[l], gss[r]));
sum[x] = sum[l] + sum[r];
```
再考虑如何维护`upd`。
`upd`的存储方式其实有两种：一种是把需要更新的值存储起来，另一种是修改时直接更新完毕，然后再打上bool标记。这里我采用的是后者。
下传也简单。将整个区间set成同一个值后，`la`、`ra`和`gss`的更新与初始化*有些相似*。
`la`和`ra`的代码不变，`gss`改成**在选全部与选一个之间取max**(题目要求必须选一个)。
没了？当然还有。
## 完整版问题
现在多了插入、删除和区间反转，维护方法相似。这里我们先考虑**每个点都有权值**后的变化。
```cpp
la[x] = max(la[l], sum[l] + (val[x]) + la[r]);
ra[x] = max(ra[r], sum[r] + (val[x]) + ra[l]);
gss[x] = max(ra[l] + (val[x]) + la[r], max(gss[l], gss[r]));
sum[x] = sum[l] + (val[x]) + sum[r];
```
其中用括号括起来的是增加的部分。
考虑同时下传反转和set两个标记。如果区间全部设置为一个值，反转也就没有意义了。所以处理顺序是set→反转。
pushdown的完整代码如下：
```cpp
void pushdown(int x) {
int l = ch[x][0], r = ch[x][1];
if (upd[x]) {
upd[x] = rev[x] = 0;
if (l) {
upd[l] = 1; val[l] = val[x];
sum[l] = val[x] * size[l];
la[l] = ra[l] = max(sum[l], 0);
gss[l] = val[x] < 0 ? val[x] : sum[l];
}
if (r) {
upd[r] = 1; val[r] = val[x];
sum[r] = val[x] * size[r];
la[r] = ra[r] = max(sum[r], 0);
gss[r] = val[x] < 0 ? val[x] : sum[r];
}
}
if (rev[x]) {
rev[l] ^= 1; rev[r] ^= 1; rev[x] = 0;
swap(la[l], ra[l]); swap(la[r], ra[r]);
swap(ch[l][0], ch[l][1]);
swap(ch[r][0], ch[r][1]);
}
}
```
## 垃圾回收
这个毒瘤题非常恶心，卡我空间，只好写个~~辣鸡~~垃圾回收。
删除的时候，把要删除的节点全部加到一个队列里。等到要插入的时候，优先使用队列里的点。
代码很好理解。
```cpp
void recycle(int x) {
if (ch[x][0]) recycle(ch[x][0]);
if (ch[x][1]) recycle(ch[x][1]);
q.push(x);
}
int newNode(int x) {
int cur;
if (q.empty()) cur = ++ncnt;
else cur = q.front(), q.pop();
ch[cur][0] = ch[cur][1] = par[cur] = 0;
val[cur] = sum[cur] = gss[cur] = x;
la[cur] = ra[cur] = max(0, x);
upd[cur] = rev[cur] = 0;
size[cur] = 1;
return cur;
}
int build(int l, int r, int *arr) {
if (l > r) return 0;
int mid = (l+r)>>1, cur = newNode(arr[mid]);
if (l == r) return cur;
if ((ch[cur][0] = build(l, mid-1, arr))) par[ch[cur][0]] = cur;
if ((ch[cur][1] = build(mid+1, r, arr))) par[ch[cur][1]] = cur;
pushup(cur);
return cur;
}
```
# 其他用途
Splay因为其超强的区间操作能力，所以也作为LCT的辅助树使用。
Splay也可以搭配~~仙人掌剖分~~**树链剖分**，把一些序列上的题目出到~~仙人掌~~**树**上。
~~~~
# 代码
下面附上我那常数巨大的代码，供参考用：
## 普通平衡树
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int ch[N][2], par[N], val[N], cnt[N], size[N], ncnt, root;
bool chk(int x) {
return ch[par[x]][1] == x;
}
void pushup(int x) {
size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
}
void rotate(int x) {
int y = par[x], z = par[y], k = chk(x), w = ch[x][k^1];
ch[y][k] = w; par[w] = y;
ch[z][chk(y)] = x; par[x] = z;
ch[x][k^1] = y; par[y] = x;
pushup(y); pushup(x);
}
void splay(int x, int goal = 0) {
while (par[x] != goal) {
int y = par[x], z = par[y];
if (z != goal) {
if (chk(x) == chk(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
if (!goal) root = x;
}
void insert(int x) {
int cur = root, p = 0;
while (cur && val[cur] != x) {
p = cur;
cur = ch[cur][x > val[cur]];
}
if (cur) {
cnt[cur]++;
} else {
cur = ++ncnt;
if (p) ch[p][x > val[p]] = cur;
ch[cur][0] = ch[cur][1] = 0;
par[cur] = p; val[cur] = x;
cnt[cur] = size[cur] = 1;
}
splay(cur);
}
void find(int x) {
int cur = root;
while (ch[cur][x > val[cur]] && x != val[cur]) {
cur = ch[cur][x > val[cur]];
}
splay(cur);
}
int kth(int k) {
int cur = root;
while (1) {
if (ch[cur][0] && k <= size[ch[cur][0]]) {
cur = ch[cur][0];
} else if (k > size[ch[cur][0]] + cnt[cur]) {
k -= size[ch[cur][0]] + cnt[cur];
cur = ch[cur][1];
} else {
splay(cur);
return cur;
}
}
}
int pre(int x) {
find(x);
if (val[root] < x) return root;
int cur = ch[root][0];
while (ch[cur][1]) cur = ch[cur][1];
splay(cur);
return cur;
}
int succ(int x) {
find(x);
if (val[root] > x) return root;
int cur = ch[root][1];
while (ch[cur][0]) cur = ch[cur][0];
splay(cur);
return cur;
}
void remove(int x) {
int last = pre(x), next = succ(x);
splay(last); splay(next, last);
int del = ch[next][0];
if (cnt[del] > 1) {
cnt[del]--;
splay(del);
}
else ch[next][0] = 0;
pushup(next), pushup(root);
}
int n, op, x;
int main() {
scanf("%d", &n);
insert(0x3f3f3f3f);
insert(0xcfcfcfcf);
while (n--) {
scanf("%d%d", &op, &x);
switch (op) {
case 1: insert(x); break;
case 2: remove(x); break;
case 3: find(x); printf("%d\n", size[ch[root][0]]); break;
case 4: printf("%d\n", val[kth(x+1)]); break;
case 5: printf("%d\n", val[pre(x)]); break;
case 6: printf("%d\n", val[succ(x)]); break;
}
}
}
```
## 文艺平衡树
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int ch[N][2], par[N], val[N], cnt[N], size[N], rev[N], root, ncnt;
int n, m, x, y;
bool chk(int x) {
return ch[par[x]][1] == x;
}
void pushup(int x) {
size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
}
void pushdown(int x) {
if (rev[x]) {
swap(ch[x][0], ch[x][1]);
rev[ch[x][0]] ^= 1;
rev[ch[x][1]] ^= 1;
rev[x] = 0;
}
}
void rotate(int x) {
int y = par[x], z = par[y], k = chk(x), w = ch[x][k^1];
ch[y][k] = w; par[w] = y;
ch[z][chk(y)] = x; par[x] = z;
ch[x][k^1] = y; par[y] = x;
pushup(y); pushup(x);
}
void splay(int x, int goal = 0) {
while (par[x] != goal) {
int y = par[x], z = par[y];
if (z != goal) {
if (chk(x) == chk(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
if (!goal) root = x;
}
void insert(int x) {
int cur = root, p = 0;
while (cur && val[cur] != x) {
p = cur;
cur = ch[cur][x > val[cur]];
}
if (cur) {
cnt[cur]++;
} else {
cur = ++ncnt;
if (p) ch[p][x > val[p]] = cur;
ch[cur][0] = ch[cur][1] = 0;
par[cur] = p; val[cur] = x;
cnt[cur] = size[cur] = 1;
}
splay(cur);
}
void find(int x) {
int cur = root;
while (ch[cur][x > val[cur]] && val[cur] != x) {
cur = ch[cur][x > val[cur]];
}
splay(cur);
}
int kth(int k) {
int cur = root; pushdown(x);
if (ch[x][0]) output(ch[x][0]);
if (val[x] && val[x] <= n) printf("%d ", val[x]);
if (ch[x][1]) output(ch[x][1]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n+1; i++) insert(i);
while (m--) {
scanf("%d%d", &x, &y);
reverse(x, y);
}
output(root);
}
```
## P2042
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1000016;
int size[N], sum[N], upd[N], rev[N], la[N], ra[N], gss[N];
int val[N], ch[N][2], par[N], ncnt, root;
queue<int> q;
void recycle(int x) {
if (ch[x][0]) recycle(ch[x][0]);
if (ch[x][1]) recycle(ch[x][1]);
q.push(x);
}
inline int newNode(int x) {
int cur;
if (q.empty()) cur = ++ncnt;
else cur = q.front(), q.pop();
ch[cur][0] = ch[cur][1] = par[cur] = 0;
val[cur] = sum[cur] = gss[cur] = x;
la[cur] = ra[cur] = max(0, x);
upd[cur] = rev[cur] = 0;
size[cur] = 1;
return cur;
}
inline bool chk(int x) {
return ch[par[x]][1] == x;
}
inline void pushup(int x) {
int l = ch[x][0], r = ch[x][1];
size[x] = size[l] + size[r] + 1;
sum[x] = sum[l] + sum[r] + val[x];
// 这里和线段树不同，线段树只有叶子上有权值，平衡树上所有点都有，必须+val[x]
la[x] = max(la[l], sum[l] + val[x] + la[r]);
ra[x] = max(ra[r], sum[r] + val[x] + ra[l]);
gss[x] = max(ra[l] + val[x] + la[r], max(gss[l], gss[r]));
}
inline void rotate(int x) {
int y = par[x], z = par[y], k = chk(x), w = ch[x][k^1];
ch[y][k] = w; par[w] = y;
ch[z][chk(y)] = x; par[x] = z;
ch[x][k^1] = y; par[y] = x;
pushup(y); pushup(x);
}
inline void pushdown(int x) {
int l = ch[x][0], r = ch[x][1];
if (upd[x]) {
upd[x] = rev[x] = 0;
if (l) {
upd[l] = 1; val[l] = val[x];
sum[l] = val[x] * size[l];
la[l] = ra[l] = max(sum[l], 0);
gss[l] = val[x] < 0 ? val[x] : sum[l];
}
if (r) {
upd[r] = 1; val[r] = val[x];
sum[r] = val[x] * size[r];
la[r] = ra[r] = max(sum[r], 0);
gss[r] = val[x] < 0 ? val[x] : sum[r];
}
}
if (rev[x]) {
rev[l] ^= 1; rev[r] ^= 1; rev[x] = 0;
swap(la[l], ra[l]); swap(la[r], ra[r]);
swap(ch[l][0], ch[l][1]);
swap(ch[r][0], ch[r][1]);
}
}
inline void splay(int x, int goal = 0) {
while (par[x] != goal) {
int y = par[x], z = par[y];
if (z != goal) {
if (chk(x) == chk(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
if (!goal) root = x;
}
int build(int l, int r, int *arr) {
if (l > r) return 0;
int mid = (l+r)>>1, cur = newNode(arr[mid]);
if (l == r) return cur;
if ((ch[cur][0] = build(l, mid-1, arr))) par[ch[cur][0]] = cur;
if ((ch[cur][1] = build(mid+1, r, arr))) par[ch[cur][1]] = cur;
pushup(cur);
return cur;
}
inline int kth(int k) {
int cur = root;
while (1) {
pushdown(cur);
if (ch[cur][0] && k <= size[ch[cur][0]]) {
cur = ch[cur][0];
} else if (k > size[ch[cur][0]] + 1) {
k -= size[ch[cur][0]] + 1;
cur = ch[cur][1];
} else {
splay(cur);
return cur;
}
}
}
inline void insert(int x, int y) {
int u = kth(x+1), v = kth(x+2);
splay(u); splay(v, u);
ch[v][0] = y; par[y] = v;
pushup(v); pushup(u);
}
inline int qsum(int x, int y) {
int u = kth(x), v = kth(x+y+1);
splay(u); splay(v, u);
return sum[ch[v][0]];
}
inline int qgss() {
return gss[root];
}
inline void remove(int x, int y) {
int u = kth(x), v = kth(x+y+1);
splay(u); splay(v, u);
recycle(ch[v][0]);
ch[v][0] = 0;
pushup(v); pushup(u);
}
inline void reverse(int x, int y) {
int u = kth(x), v = kth(x+y+1);
splay(u); splay(v, u);
int w = ch[v][0];
if (!upd[w]) {
rev[w] ^= 1;
swap(ch[w][0], ch[w][1]);
swap(la[w], ra[w]);
pushup(v); pushup(u);
}
}
inline void update(int x, int y, int z) {
int u = kth(x), v = kth(x+y+1);
splay(u); splay(v, u);
int w = ch[v][0];
upd[w] = 1; val[w] = z; sum[w] = size[w] * z;
la[w] = ra[w] = max(0, sum[w]);
gss[w] = z < 0 ? z : sum[w];
pushup(v); pushup(u);
}
int n, m, arr[N], c, x, y, z;
char buf[32];
int main() {
// freopen("I:\\OI\\Y\\0803\\5.in", "r", stdin);
// freopen("I:\\OI\\Y\\0803\\5s.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 2; i <= n+1; i++) {
scanf("%d", arr+i);
}
gss[0] = val[0] = 0xcfcfcfcf;
arr[1] = arr[n += 2] = 0xcfcfcfcf;
build(1, n, arr); root = 1;
while (m--) {
// debug();
scanf("%s", buf);
switch ((buf[2] + buf[1]) ^ *buf) {
case 'G'^('E'+'T'):
scanf("%d%d", &x,
while (1) {
pushdown(cur);
if (ch[cur][0] && k <= size[ch[cur][0]]) {
cur = ch[cur][0];
} else if (k > size[ch[cur][0]] + cnt[cur]) {
k -= size[ch[cur][0]] + cnt[cur];
cur = ch[cur][1];
} else {
splay(cur);
return cur;
}
}
}
void reverse(int l, int r) {
int x = kth(l), y = kth(r+2);
splay(x); splay(y, x);
rev[ch[y][0]] ^= 1;
}
int pre(int x) {
find(x);
if (val[root] < x) return root;
int cur = ch[root][0];
while (ch[cur][1]) cur = ch[cur][1];
splay(cur);
return cur;
}
int succ(int x) {
find(x);
if (val[root] > x) return root;
int cur = ch[root][1];
while (ch[cur][0]) cur = ch[cur][0];
splay(cur);
return cur;
}
void output(int x) {
pushdown(x);
if (ch[x][0]) output(ch[x][0]);
if (val[x] && val[x] <= n) printf("%d ", val[x]);
if (ch[x][1]) output(ch[x][1]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n+1; i++) insert(i);
while (m--) {
scanf("%d%d", &x, &y);
reverse(x, y);
}
output(root);
}
```
## P2042
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1000016;
int size[N], sum[N], upd[N], rev[N], la[N], ra[N], gss[N];
int val[N], ch[N][2], par[N], ncnt, root;
queue<int> q;
void recycle(int x) {
if (ch[x][0]) recycle(ch[x][0]);
if (ch[x][1]) recycle(ch[x][1]);
q.push(x);
}
inline int newNode(int x) {
int cur;
if (q.empty()) cur = ++ncnt;
else cur = q.front(), q.pop();
ch[cur][0] = ch[cur][1] = par[cur] = 0;
val[cur] = sum[cur] = gss[cur] = x;
la[cur] = ra[cur] = max(0, x);
upd[cur] = rev[cur] = 0;
size[cur] = 1;
return cur;
}
inline bool chk(int x) {
return ch[par[x]][1] == x;
}
inline void pushup(int x) {
int l = ch[x][0], r = ch[x][1];
size[x] = size[l] + size[r] + 1;
sum[x] = sum[l] + sum[r] + val[x];
// 这里和线段树不同，线段树只有叶子上有权值，平衡树上所有点都有，必须+val[x]
la[x] = max(la[l], sum[l] + val[x] + la[r]);
ra[x] = max(ra[r], sum[r] + val[x] + ra[l]);
gss[x] = max(ra[l] + val[x] + la[r], max(gss[l], gss[r]));
}
inline void rotate(int x) {
int y = par[x], z = par[y], k = chk(x), w = ch[x][k^1];
ch[y][k] = w; par[w] = y;
ch[z][chk(y)] = x; par[x] = z;
ch[x][k^1] = y; par[y] = x;
pushup(y); pushup(x);
}
inline void pushdown(int x) {
int l = ch[x][0], r = ch[x][1];
if (upd[x]) {
upd[x] = rev[x] = 0;
if (l) {
upd[l] = 1; val[l] = val[x];
sum[l] = val[x] * size[l];
la[l] = ra[l] = max(sum[l], 0);
gss[l] = val[x] < 0 ? val[x] : sum[l];
}
if (r) {
upd[r] = 1; val[r] = val[x];
sum[r] = val[x] * size[r];
la[r] = ra[r] = max(sum[r], 0);
gss[r] = val[x] < 0 ? val[x] : sum[r];
}
}
if (rev[x]) {
rev[l] ^= 1; rev[r] ^= 1; rev[x] = 0;
swap(la[l], ra[l]); swap(la[r], ra[r]);
swap(ch[l][0], ch[l][1]);
swap(ch[r][0], ch[r][1]);
}
}
inline void splay(int x, int goal = 0) {
while (par[x] != goal) {
int y = par[x], z = par[y];
if (z != goal) {
if (chk(x) == chk(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
if (!goal) root = x;
}
int build(int l, int r, int *arr) {
if (l > r) return 0;
int mid = (l+r)>>1, cur = newNode(arr[mid]);
if (l == r) return cur;
if ((ch[cur][0] = build(l, mid-1, arr))) par[ch[cur][0]] = cur;
if ((ch[cur][1] = build(mid+1, r, arr))) par[ch[cur][1]] = cur;
pushup(cur);
return cur;
}
inline int kth(int k) {
int cur = root;
while (1) {
pushdown(cur);
if (ch[cur][0] && k <= size[ch[cur][0]]) {
cur = ch[cur][0];
} else if (k > size[ch[cur][0]] + 1) {
k -= size[ch[cur][0]] + 1;
cur = ch[cur][1];
} else {
splay(cur);
return cur;
}
}
}
inline void insert(int x, int y) {
int u = kth(x+1), v = kth(x+2);
splay(u); splay(v, u);
ch[v][0] = y; par[y] = v;
pushup(v); pushup(u);
}
inline int qsum(int x, int y) {
int u = kth(x), v = kth(x+y+1);
splay(u); splay(v, u);
return sum[ch[v][0]];
}
inline int qgss() {
return gss[root];
}
inline void remove(int x, int y) {
int u = kth(x), v = kth(x+y+1);
splay(u); splay(v, u);
recycle(ch[v][0]);
ch[v][0] = 0;
pushup(v); pushup(u);
}
inline void reverse(int x, int y) {
int u = kth(x), v = kth(x+y+1);
splay(u); splay(v, u);
int w = ch[v][0];
if (!upd[w]) {
rev[w] ^= 1;
swap(ch[w][0], ch[w][1]);
swap(la[w], ra[w]);
pushup(v); pushup(u);
}
}
inline void update(int x, int y, int z) {
int u = kth(x), v = kth(x+y+1);
splay(u); splay(v, u);
int w = ch[v][0];
upd[w] = 1; val[w] = z; sum[w] = size[w] * z;
la[w] = ra[w] = max(0, sum[w]);
gss[w] = z < 0 ? z : sum[w];
pushup(v); pushup(u);
}
int n, m, arr[N], c, x, y, z;
char buf[32];
int main() {
// freopen("I:\\OI\\Y\\0803\\5.in", "r", stdin);
// freopen("I:\\OI\\Y\\0803\\5s.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 2; i <= n+1; i++) {
scanf("%d", arr+i);
}
gss[0] = val[0] = 0xcfcfcfcf;
arr[1] = arr[n += 2] = 0xcfcfcfcf;
build(1, n, arr); root = 1;
while (m--) {
// debug();
scanf("%s", buf);
switch ((buf[2] + buf[1]) ^ *buf) {
case 'G'^('E'+'T'):
scanf("%d%d", &x, &y);
printf("%d\n", qsum(x, y));
break;
case 'M'^('A'+'X'):
printf("%d\n", qgss());
break;
case 'R'^('E'+'V'):
scanf("%d%d", &x, &y);
reverse(x, y);
break;
case 'M'^('A'+'K'):
scanf("%d%d%d", &x, &y, &z);
update(x, y, z);
break;
case 'D'^('E'+'L'):
scanf("%d%d", &x, &y);
remove(x, y);
break;
case 'I'^('N'+'S'):
scanf("%d%d", &x, &y);
memset(arr, 0, sizeof arr);
for (int i = 1; i <= y; i++) {
scanf("%d", arr+i);
}
insert(x, build(1, y, arr));
break;
}
}
}
```
# **↓↓↓↓↓下面的都是dalao↓↓↓↓↓**