模板及讲解
Splay
Splay 就是平衡树。
Splay 的原理
例题 (不涉及区间操作)：Bzoj 3224
需要建立一个虚节点 0 作为初始根，加入一个正无穷和负无穷免除边界困扰。(类似 set)
核心操作：
void rotate(int x)：对 $x$ 进行旋转操作void splay(int x, int gl = 0)：将 $x$rotate到 $gl$ 的孩子
辅助操作：
bool rel(int x)：返回 $x$ 在 $fa[x]$ 中的左右位置void pushup(int x)：维护 $x$ 点信息 (更新)
实现操作：
void insert(int x)：插入一个值为 $x$ 的节点并转到根void find(int x)：找一个值为 $x$ 的节点转到根，不存在则返回当前数的前驱或后继int kth(int k)：找值第 $k$ 大数int rnk(int x)：值 $x$ 的排名int pre(int x)：值前驱int succ(int x)：值后继void remove(int x)：删除一个值为 $x$ 的节点，若点还存在，转到根辅助操作实现
bool rel(int x) {return ch[fa[x]][1] == x;} // x 点在父亲点的位置 (x 点是不是父亲点的右孩子)
void pushup(int x) {siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];}
核心操作实现
rotate：
对 $x$ 进行旋转操作。
Splay使用旋转保持平衡。Splay旋转后，中序遍历和Splay的合法性不变。但是信息要重新合并
图一为原树，图二为旋转完的树。
绿边为新增边，红边为删除边，蓝边为存在边。
void rotate(int x) { // 旋转操作
int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
ch[z][rel(y)] = x, fa[x] = z; // 将爷爷节点与自己相连
ch[y][k] = w, fa[w] = y; // 将自己的孩子给父节点
ch[x][k ^ 1] = y, fa[y] = x; // 将父节点接到自己孩子
pushup(y), pushup(x); // 破坏了结构记得 pushup
}
splay：
将 $x$
rotate到 $gl$ 的孩子
将某个点通过 rotate 转到某个点的孩子。
容易想到一直 rotate 然后判断，这是单旋splay。但是这样由于一条单链旋转完以后还是单链，会被卡。
所以我们尝试优化，如果当前自身点、父亲节点、爷爷节点三点一线，则先选择父亲节点，再选择本节点。
void splay(int x, int gl = 0) { // splay 操作 -> 将 x 节点转到 gl 节点孩子 ，并且可以用作更新信息
while (fa[x] != gl) { // 一直旋转到目标节点的儿子
int y = fa[x], z = fa[y];
if (z != gl) { // 爷爷节点不是目标节点，否则直接旋转
if (rel(x) == rel(y)) rotate(y); else rotate(x); // 自身、父亲、爷爷三点一线，则先旋转父亲节点
}
rotate(x); // 旋转自身
}
if (!gl) rt = x; // 如果旋转到根则更新 rt
}
实现操作实现
insert：
插入一个值为 $x$ 的节点并转到根
从根走下去找这个数应该在的位置，然后如果存在则增加计数器，否则新建节点。
注意将节点转到根，这样才能更新沿路的信息，并且保证了复杂度。
void insert(int x) { // 插入一个值为 x 的节点并转到根
int cur = rt, p = 0; // cur 当前节点， p 为 cur 父亲
while (cur && val[cur] != x) p = cur, cur = ch[cur][x > val[cur]]; // 找插入位置
if (cur) ++cnt[cur]; else { // 找到插入位置，如果已经有数则 cnt 加一即可，否则新建节点
cur = ++ncnt;
val[cur] = x, fa[cur] = p, ch[cur][0] = ch[cur][1] = 0, cnt[cur] = siz[cur] = 1;
ch[p][x > val[p]] = cur;
}
splay(cur); // splay 到根，以免加入节点后拉出一条链 + 更新信息
}
find：
找一个值为 $x$ 的节点转到根，不存在则返回当前数的前驱或后继
从根走下去找这个数应该在的位置，找不到则返回的是前驱或后继。(无法确定，分类讨论即可)
void find(int x) { // 找一个值为 x 的节点转到根，不存在则返回当前数的前驱或后继
int cur = rt;
while (ch[cur][x > val[cur]] && val[cur] != x) cur = ch[cur][x > val[cur]];
splay(cur);
}
kth：
找值第 $k$ 大数
从根走下去找，很经典的问题，注意当前根节点的cnt值
int kth(int k) { // 找值第 k 大数
int cur = rt;
while (1) {
if (k <= siz[ch[cur][0]]) cur = ch[cur][0];
else if (k > siz[ch[cur][0]] + cnt[cur]) k -= siz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
else return cur;
}
}
rnk:
值 $x$ 的排名
先将值为 $x$ 的点转到根，根节点的左子树大小即为该值排名，不加一因为有虚节点。
int rnk(int x) { // 值 x 的排名
find(x); // splay 值为 x 的节点到根后左子树的大小即为值 x 排名
return siz[ch[rt][0]];
}
pre:
值前驱
先将值为 $x$ 的节点 splay 到根, 再找根左子树最右边的值即为前驱
注意不存在 $x$ 值节点时判一下根节点大小
int pre(int x) { // 值前驱
find(x); // 先将值为 x 的节点 splay 到根
if (val[rt] < x) return rt; // 找不到这样的节点则直接返回根
int cur = ch[rt][0]; // 找根左子树最右边的值即为前驱
while (ch[cur][1]) cur = ch[cur][1];
return cur;
}
succ:
值后继
先将值为 $x$ 的节点 splay 到根, 再找根右子树最左边的值即为后继
注意不存在 $x$ 值节点时判一下根节点大小
int succ(int x) { // 值后继
find(x); // 先将值为 x 的节点 splay 到根
if (val[rt] > x) return rt; // 找不到这样的节点则直接返回根
int cur = ch[rt][1]; // 找根右子树最左边的值即为前驱
while (ch[cur][0]) cur = ch[cur][0];
return cur;
}
remove:
删除一个值为 $x$ 的节点，若点还存在，转到根
将前驱转到根，后继转到根的右孩子，然后删除，如果当前节点次数多于1将他splay到根，否则维护前驱、后继的信息。
为什么可以这样做看图即可。
void remove(int x) { // 删除一个值为 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(last);
// 记得信息的更新上传
}
Bzoj 3224完整代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 200005, INF = 2000000005;
int ch[MAXN][2], fa[MAXN], val[MAXN], cnt[MAXN], siz[MAXN], ncnt, rt, n;
// splay 数组，父亲节点，节点值，节点值个数，节点子树大小，节点总数，根
bool rel(int x) {return ch[fa[x]][1] == x;} // x 点在父亲点的位置 (x 点是不是父亲点的右孩子)
void pushup(int x) {siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];}
void rotate(int x) { // 旋转操作
int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
ch[z][rel(y)] = x, fa[x] = z; // 将爷爷节点与自己相连
ch[y][k] = w, fa[w] = y; // 将自己的孩子给父节点
ch[x][k ^ 1] = y, fa[y] = x; // 将父节点接到自己孩子
pushup(y), pushup(x); // 破坏了结构记得 pushup
}
void splay(int x, int gl = 0) { // splay 操作 -> 将 x 节点转到 gl 节点孩子 ，并且可以用作更新信息
while (fa[x] != gl) { // 一直旋转到目标节点的儿子
int y = fa[x], z = fa[y];
if (z != gl) { // 爷爷节点不是目标节点，否则直接旋转
if (rel(x) == rel(y)) rotate(y); else rotate(x); // 自身、父亲、爷爷三点一线，则先旋转父亲节点
}
rotate(x); // 旋转自身
}
if (!gl) rt = x; // 如果旋转到根则更新 rt
}
void insert(int x) { // 插入一个值为 x 的节点并转到根
int cur = rt, p = 0; // cur 当前节点， p 为 cur 父亲
while (cur && val[cur] != x) p = cur, cur = ch[cur][x > val[cur]]; // 找插入位置
if (cur) ++cnt[cur]; else { // 找到插入位置，如果已经有数则 cnt 加一即可，否则新建节点
cur = ++ncnt;
val[cur] = x, fa[cur] = p, ch[cur][0] = ch[cur][1] = 0, cnt[cur] = siz[cur] = 1;
ch[p][x > val[p]] = cur;
}
splay(cur); // splay 到根，以免加入节点后拉出一条链 + 更新信息
}
void find(int x) { // 找一个值为 x 的节点转到根，不存在则返回当前数的前驱或后继
int cur = rt;
while (ch[cur][x > val[cur]] && val[cur] != x) cur = ch[cur][x > val[cur]];
splay(cur);
}
int kth(int k) { // 找值第 k 大数
int cur = rt;
while (1) {
if (k <= siz[ch[cur][0]]) cur = ch[cur][0];
else if (k > siz[ch[cur][0]] + cnt[cur]) k -= siz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
else return cur;
}
}
int rnk(int x) { // 值 x 的排名
find(x); // splay 值为 x 的节点到根后左子树的大小即为值 x 排名
return siz[ch[rt][0]];
}
int pre(int x) { // 值前驱
find(x); // 先将值为 x 的节点 splay 到根
if (val[rt] < x) return rt; // 找不到这样的节点则直接返回根
int cur = ch[rt][0]; // 找根左子树最右边的值即为前驱
while (ch[cur][1]) cur = ch[cur][1];
return cur;
}
int succ(int x) { // 值后继
find(x); // 先将值为 x 的节点 splay 到根
if (val[rt] > x) return rt; // 找不到这样的节点则直接返回根
int cur = ch[rt][1]; // 找根右子树最左边的值即为前驱
while (ch[cur][0]) cur = ch[cur][0];
return cur;
}
void remove(int x) { // 删除一个值为 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(last);
// 记得信息的更新上传
}
void clean() {
ms(fa, 0), ms(cnt, 0), ms(val, 0), ms(siz, 0), rt = ncnt = 0;
}
int solve() {
clean();
scanf("%d", &n);
insert(INF), insert(-INF); // 插入最大最小值
while (n--) {
int opt, x;
scanf("%d%d", &opt, &x);
switch (opt) {
case 1: insert(x); break ;
case 2: remove(x); break ;
case 3: printf("%d\n", rnk(x)); 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 ;
}
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
写时注意：
1、splay中不要忘记写换根 if (gl == 0) rt = x;
2、splay中最后一个rotate(x)写在判断外面
3、rotate中rel(x)一定要预处理，因为之后会被改变
4、insert中不要忘记转到根，remove中不要忘记转到根+更新信息
5、insert 和 find 中while注意判断中的 $val$ 怎么写
6、kth中if (k <= siz[ch[cur][0]])的<=
Splay 维护区间序列
例题：Bzoj 3223
给定$n$长数组$a_i$，$m$次操作翻转区间$[l,r]$
$n,m \leq 10^5。$
本题是维护序列，与上面的不同。我们将序列值存在 $val$ 中，舍弃二叉排序树的性质，保留中序遍历，中序遍历对应原数组，显然 Splay 中 $x$ 点为$[x,x]$，左子树为$[1, x)$，右子树为$(x, n]$，则 Splay 中求得的 $k$ 大值为序列 $k$ 位置的值，区间类似。
由于旋转操作不影响中序遍历，所以这样的问题可以用 splay 来完成。
我们可以运用线段树中lazy的技巧来做splay的区间信息维护。
标记下放
void pushdown(int x) {
if (lazy[x]) swap(ch[x][0], ch[x][1]), lazy[ch[x][0]] ^= 1, lazy[ch[x][1]] ^= 1, lazy[x] = 0;
}
选择单点
本题不需要，其实序列的单点位置就是第$k$大
选择区间
将$l-1$大的位置找出来，$r+1$大的位置找出来
将$l-1$大的位置转到根，$l-1$大的位置转到根的孩子，则$r+1$大的位置的左孩子是区间$[l,r]$
void rev(int l, int r) {
int lb = kth(l), rb = kth(r + 2); // 无穷小虚节点在最前面，所以加一
splay(lb), splay(rb, lb);
lazy[ch[rb][0]] ^= 1;
}
输出答案
由于中序遍历始终有序，直接中序遍历即可
void print(int x) {
pushdown(x);
if (ch[x][0]) print(ch[x][0]);
if (1 <= val[x] && val[x] <= n) printf("%d ", val[x]);
if (ch[x][1]) print(ch[x][1]);
}
标记下放注意事项
1、调用rel(x)之前一定要pushdown(x)
2、调用ch[x][0/1]之前一定要pushdown(x)
3、splay 维护区间不要用 insert
建树
因为没有二叉排序树性质，无法根据权值大小建树。
所以增加一个函数，每次取$mid=\frac{l+r}2$点作根然后遍历两边建点。
最后返回根节点的编号
int build(int p, int l, int r) {
int mid = (l + r) >> 1;
if (l > r) return 0;
int cur = ++ncnt;
ch[cur][0] = ch[cur][1] = 0, fa[cur] = p, siz[cur] = 1, val[cur] = mid - 1;
if (l == r) return cur;
ch[cur][0] = build(cur, l, mid - 1), ch[cur][1] = build(cur, mid + 1, r);
pushup(cur);
return cur;
}
Bzoj 3223完整代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
int n, m;
int ch[MAXN][2], val[MAXN], siz[MAXN], fa[MAXN], lazy[MAXN], ncnt, rt;
bool rel(int x) {return ch[fa[x]][1] == x;}
void pushup(int x) {siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;}
void pushdown(int x) {if (lazy[x]) swap(ch[x][0], ch[x][1]), lazy[ch[x][0]] ^= 1, lazy[ch[x][1]] ^= 1, lazy[x] = 0;}
void rotate(int x) {
pushdown(fa[x]), pushdown(x);
int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
ch[z][rel(y)] = x, fa[x] = z;
ch[y][k] = w, fa[w] = y;
ch[x][k ^ 1] = y, fa[y] = x;
pushup(y), pushup(x);
}
void splay(int x, int gl = 0) {
while (fa[x] != gl) {
pushdown(fa[x]);
pushdown(x);
int y = fa[x], z = fa[y];
if (z != gl) {
if (rel(x) == rel(y)) rotate(y); else rotate(x);
}
rotate(x);
}
if (gl == 0) rt = x;
}
int build(int p, int l, int r) {
int mid = (l + r) >> 1;
if (l > r) return 0;
int cur = ++ncnt;
ch[cur][0] = ch[cur][1] = 0, fa[cur] = p, siz[cur] = 1, val[cur] = mid - 1;
if (l == r) return cur;
ch[cur][0] = build(cur, l, mid - 1), ch[cur][1] = build(cur, mid + 1, r);
pushup(cur);
return cur;
}
int kth(int k) {
int cur = rt;
while (1) {
pushdown(cur);
if (k <= siz[ch[cur][0]]) cur = ch[cur][0];
else if (k > siz[ch[cur][0]] + 1) k -= siz[ch[cur][0]] + 1, cur = ch[cur][1];
else return cur;
}
}
void rev(int l, int r) {
int lb = kth(l), rb = kth(r + 2);
splay(lb), splay(rb, lb);
lazy[ch[rb][0]] ^= 1;
}
void print(int x) {
pushdown(x);
if (ch[x][0]) print(ch[x][0]);
if (1 <= val[x] && val[x] <= n) printf("%d ", val[x]);
if (ch[x][1]) print(ch[x][1]);
}
void clean() {
ms(ch, 0), ms(val, 0), ms(siz, 0), ms(fa, 0), ms(lazy, 0), ncnt = rt = 0;
}
int solve() {
clean();
scanf("%d%d", &n, &m);
//for (int i = 0; i <= n + 1; ++i) insert(i); 维护区间不要用 insert，本题碰巧权值与下标一样
rt = build(0, 1, n + 2); // [1, n + 2] 避免与 0 冲突
while (m--) {
int l, r; scanf("%d%d", &l, &r);
rev(l, r);
}
print(rt);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
Splay 维护区间序列终极例题
请写一个程序，要求维护一个数列，支持以下 $6$ 种操作：
请注意，格式栏中的下划线表示实际输入文件中的空格.png)
Splay 可以用来维护区间的信息，则可以像线段树一样打标记。
上一题只有翻转标记，而这一题多了很多标记
我们维护$sum, ls, rs, gss$分别为区间和、最大前缀和、最大后缀和，最长字段和。
标记$lazy, upd$分别为翻转标记和更新标记。
初始化
注意字段和一定要选一个元素
val[cur] = v, sum[cur] = v, ls[cur] = rs[cur] = max(0, v), gss[cur] = v, upd[cur] = lazy[cur] = 0;
pushup
注意 splay 上每个点有 $val$，要记得加上
void pushup(int x) {
int l = ch[x][0], r = ch[x][1];
siz[x] = siz[l] + siz[r] + 1;
sum[x] = sum[l] + sum[r] + val[x];
ls[x] = max(ls[l], sum[l] + val[x] + ls[r]);
rs[x] = max(rs[r], sum[r] + val[x] + rs[l]);
gss[x] = max(rs[l] + val[x] + ls[r], max(gss[l], gss[r]));
}
pushdown
注意如果当前又有更新标记又有翻转标记，则只用更新。而翻转需要将ls,rs一同翻转，显然。
void pushdown(int x) {
int l = ch[x][0], r = ch[x][1];
if (upd[x]) {
if (l) val[l] = val[x], upd[l] = 1, sum[l] = val[x] * siz[l], ls[l] = rs[l] = max(sum[l], 0), gss[l] = max(val[x], sum[l]);
if (r) val[r] = val[x], upd[r] = 1, sum[r] = val[x] * siz[r], ls[r] = rs[r] = max(sum[r], 0), gss[r] = max(val[x], sum[r]);
upd[x] = lazy[x] = 0;
}
if (lazy[x]) {
lazy[l] ^= 1, lazy[r] ^= 1;
swap(ch[l][0], ch[l][1]), swap(ch[r][0], ch[r][1]);
swap(ls[l], rs[l]), swap(ls[r], rs[r]); // 注意
lazy[x] = 0;
}
}
修改操作
注意如果翻转时当前有更新标记，则不需要打翻转标记，注意标时即改。
void rev(int l, int r) {
int lb = kth(l), rb = kth(r + 2);
splay(lb), splay(rb, lb);
int gg = ch[rb][0];
if (!upd[gg]) lazy[gg] ^= 1, swap(ch[gg][0], ch[gg][1]), swap(ls[gg], rs[gg]), pushup(rb), pushup(lb);
}
void update(int l, int r, int v) {
int lb = kth(l), rb = kth(r + 2);
splay(lb), splay(rb, lb);
int gg = ch[rb][0];
upd[gg] = 1, val[gg] = v, sum[gg] = v * siz[gg], ls[gg] = rs[gg] = max(sum[gg], 0), gss[gg] = max(v, sum[gg]);
pushup(rb), pushup(lb);
}
辣鸡清理
本题卡内存，所以要把删除后的节点编号用队列存起来然后之后新建节点时可以用。
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 v) { // 新建节点
int cur;
if (q.empty()) cur = ++ncnt; else cur = q.front(), q.pop();
ch[cur][0] = ch[cur][1] = 0, fa[cur] = 0, siz[cur] = 1, val[cur] = v, sum[cur] = v, upd[cur] = lazy[cur] = 0, ls[cur] = rs[cur] = max(0, v), gss[cur] = v;
return cur;
}
void remove(int l, int r) { // 删除节点
int lb = kth(l), rb = kth(r + 2);
splay(lb), splay(rb, lb);
recycle(ch[rb][0]), ch[rb][0] = 0; // 调用
pushup(rb), pushup(lb);
}
插入：新建一棵 splay 插到原树上
删除：提取区间以后打删除标记，注意卡内存用辣鸡回收优化
修改：提取区间以后打标记，注意这里标记都是标时即改
翻转：提取区间以后打标记，若有修改标记则无需做任何事情
求和：提取区间输出区间和
求最长字段和：维护 $ls, rs$分别表示左起最长区间和，右起最长区间和。
则可以通过维护得到。
完整代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 1000000 + 5, INF = 1000000000;
int n, m, arr[MAXN];
int ch[MAXN][2], fa[MAXN], siz[MAXN], val[MAXN], ls[MAXN], rs[MAXN], gss[MAXN], sum[MAXN], lazy[MAXN], upd[MAXN], rt, ncnt;
char s[10];
queue<int > q;
int rel(int x) {return ch[fa[x]][1] == x;}
void pushup(int x) {
int l = ch[x][0], r = ch[x][1];
siz[x] = siz[l] + siz[r] + 1;
ls[x] = max(ls[l], sum[l] + ls[r] + val[x]);
rs[x] = max(rs[r], sum[r] + rs[l] + val[x]);
sum[x] = sum[l] + sum[r] + val[x];
gss[x] = max(max(gss[l], gss[r]), rs[l] + ls[r] + val[x]);
}
void pushdown(int x) {
int l = ch[x][0], r = ch[x][1];
if (upd[x]) {
upd[l] = upd[r] = 1;
if (l) val[l] = val[x], sum[l] = val[x] * siz[l], ls[l] = rs[l] = max(sum[l], 0), gss[l] = max(sum[l], val[x]);
if (r) val[r] = val[x], sum[r] = val[x] * siz[r], ls[r] = rs[r] = max(sum[r], 0), gss[r] = max(sum[r], val[x]);
upd[x] = lazy[x] = 0;
}
if (lazy[x]) {
lazy[l] ^= 1, lazy[r] ^= 1;
swap(ch[l][0], ch[l][1]), swap(ch[r][0], ch[r][1]);
swap(ls[l], rs[l]), swap(ls[r], rs[r]);
lazy[x] = 0;
}
}
void rotate(int x) {
pushdown(fa[x]), pushdown(x);
int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
ch[z][rel(y)] = x, fa[x] = z;
ch[y][k] = w, fa[w] = y;
ch[x][k ^ 1] = y, fa[y] = x;
pushup(y), pushup(x);
}
void splay(int x, int gl = 0) {
while (fa[x] != gl) {
pushdown(fa[x]), pushdown(x);
int y = fa[x], z = fa[y];
if (z != gl) {
if (rel(x) == rel(y)) rotate(y); else rotate(x);
}
rotate(x);
}
if (!gl) rt = x;
}
int kth(int k) {
int cur = rt;
while (1) {
pushdown(cur);
if (k <= siz[ch[cur][0]]) cur = ch[cur][0];
else if (k > siz[ch[cur][0]] + 1) k -= siz[ch[cur][0]] + 1, cur = ch[cur][1];
else return cur;
}
}
int newNode(int v) {
int cur;
if (q.empty()) cur = ++ncnt; else cur = q.front(), q.pop();
ch[cur][0] = ch[cur][1] = 0, fa[cur] = 0, siz[cur] = 1, val[cur] = v, ls[cur] = rs[cur] = max(v, 0), gss[cur] = sum[cur] = v, lazy[cur] = upd[cur] = 0;
return cur;
}
int build(int l, int r) {
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))) fa[ch[cur][0]] = cur;
if ((ch[cur][1] = build(mid + 1, r))) fa[ch[cur][1]] = cur;
pushup(cur);
return cur;
}
void recycle(int x) {
if (ch[x][0]) recycle(ch[x][0]);
if (ch[x][1]) recycle(ch[x][1]);
q.push(x);
}
void insert(int x, int gg) {
int lb = kth(x + 1), rb = kth(x + 2);
splay(lb), splay(rb, lb);
fa[gg] = rb, ch[rb][0] = gg; // important
pushup(rb), pushup(lb);
}
void remove(int l, int r) {
int lb = kth(l), rb = kth(r + 2);
splay(lb), splay(rb, lb);
int del = ch[rb][0];
recycle(del), ch[rb][0] = 0;
pushup(rb), pushup(lb);
}
void rev(int l, int r) {
int lb = kth(l), rb = kth(r + 2);
splay(lb), splay(rb, lb);
int gg = ch[rb][0];
if (!upd[gg]) lazy[gg] ^= 1, swap(ch[gg][0], ch[gg][1]), swap(ls[gg], rs[gg]), pushup(rb), pushup(lb);
}
void update(int l, int r, int v) {
int lb = kth(l), rb = kth(r + 2);
splay(lb), splay(rb, lb);
int gg = ch[rb][0];
upd[gg] = 1, val[gg] = v, sum[gg] = v * siz[gg], ls[gg] = rs[gg] = max(0, sum[gg]), gss[gg] = max(v, sum[gg]);
pushup(rb), pushup(lb);
}
int qsum(int l, int r) {
int lb = kth(l), rb = kth(r + 2);
splay(lb), splay(rb, lb);
return sum[ch[rb][0]];
}
int qmax() {return gss[rt];}
void clean() {
rt = ncnt = 0;
ms(ch, 0), ms(fa, 0), ms(siz, 0), ms(val, 0), ms(ls, 0), ms(rs, 0), ms(gss, 0), ms(sum, 0), ms(lazy, 0), ms(upd, 0);
gss[0] = val[0] = -INF;
}
int solve() {
clean();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &arr[i + 1]);
arr[1] = arr[n + 2] = -INF, rt = build(1, n + 2);
while (m--) {
scanf("%s", s);
if (s[0] == 'I') { // insert
int pos, tot; scanf("%d%d", &pos, &tot);
for (int i = 1; i <= tot; ++i) scanf("%d", &arr[i]);
insert(pos, build(1, tot));
}
if (s[0] == 'D') { // delete
int pos, tot; scanf("%d%d", &pos, &tot);
remove(pos, pos + tot - 1);
}
if (s[0] == 'M' && s[5] == 'S') { // update
int pos, tot, c; scanf("%d%d%d", &pos, &tot, &c);
update(pos, pos + tot - 1, c);
}
if (s[0] == 'R') { // rev
int pos, tot; scanf("%d%d", &pos, &tot);
rev(pos, pos + tot - 1);
}
if (s[0] == 'G') { // qsum
int pos, tot; scanf("%d%d", &pos, &tot);
printf("%d\n", qsum(pos, pos + tot - 1));
}
if (s[0] == 'M' && s[4] == 'S') { // qmax
printf("%d\n", qmax());
}
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
写时注意：
1、检查每个函数是否 pushup、pushdown
2、对维护值进行修改等时，对照变量数组列表先数有没有漏，再看标记维护有没有错
3、序列区间最好都建在 $[1,n+2]$，避免与$0$冲突，加上虚节点非常有用
4、维护序列一定要用$build$函数
常见题型
1、名次树
Luogu3765
2、Splay森林
Bzoj 2733
3、维护序列
Bzoj 1500
