说到平衡树，很多人的第一印象就是：
- 难学（知识点真多）
- 难懂（特别是“旋转”和证明）
- 难调（我的某个教练刚学平衡树的时候调了七个小时）
下面我们就来从0开始讲平衡树。
（注：网上大多数人说到“平衡树”默认指的是“Splay”而不是其他算法）
定义
其实平衡树（Balance Tree，简称BT）不算一种算法，而是一种统称。
平衡树顾名思义就是非常平衡的树。
比如说这棵树就非常不平衡：
而这棵树就比较平衡：
如果说的更形式化，平衡就意味着，对于每个点，其所有子树的大小差都不超过 $1$。
具体而言，对于每个点 $x$，如果我们把其所有儿子 $to$ 的子树大小都列出来，那么这个数组内最大值和最小值差不超过 $1$。
而且，大多数平衡树都是二叉树，这一点是为了方便操作和设计算法。
种类
听完上面的定义，你就知道了，平衡树就是一类树状数据结构的统称。
下面就来列举一下这类数据结构都有哪些，以及这些数据结构的简介。
二叉搜索树（Binary Search Tree，简称BST）
大多数平衡树的前置算法，这也就意味着，大多数的平衡树都是基于BST并进行优化、扩展后得到的算法。
而BST也是线段树（Segment Tree，部分情况下会简称为ST）进行扩展后的算法。
具体而言，权值线段树和BST都可以维护有序集合，但有时候只能用BST解决。
BST其实就是把权值“当做”节点编号（讲的时候一般就这么讲，但写的时候不能这么写，是把权值存入该节点的结构体内）。
然后对于每个点，它都有最多 $2$ 个儿子，左儿子权值 $<$ 当前点权值 $<$ 右儿子权值。
这样就可以方便查找。
优点：代码好写，容易讲明白
缺点：解决题型少，需要写定期重构（又被称作“替罪羊树思想”），复杂度高
Treap（名字不是一个单词，而是两个单词Tree和Heap的结合）
这个算法给每个节点都添加了一个“优先级”，并让“优先级”满足小/大根堆的性质。
并且，这里还通过“旋转”操作（最头疼的地方来了）让树尽量平衡，这样会让树高稳定在 $O(\log n)$ 级别。
（不过注意，在最坏情况下，复杂度会达到 $O(n)$，所以 $O(\log n)$ 只是期望）
这样，复杂度就降下来了。
优点：复杂度低，比较容易理解，解决题型多，且容易被识别出
缺点：比较难写，细节较多，复杂度难证明
Splay（本意为“张开”但这里不是这个意思）
这个算法对上面的“旋转”操作又做了一遍扩展，让其能够解决子串翻转问题。
而且，由于它也会让整棵树尽量平衡，所以树高还是会稳定在 $O(\log n)$ 级别。
（这里的 $O(\log n)$ 应该也是期望）
优点：复杂度低，解决题型多，且容易被识别出
缺点：非常难写，细节贼多，非常难理解，复杂度依然很难证明
依次讲解
接下来来分别看每种算法的实现与解决题型
解决题型
下面默认都要解决P3369这道题。
这种题型就是上面说的“维护集合”的题目。
下面来看如何解决。
权值线段树
看到这道题，很多人都会想到权值线段树（不过要先离散化）。
我们就维护当前每个值域内的值个数。
然后，可以发现，每种询问分别可以这样解决：
- 单点修改
- 单点修改
- 区间求和
- 线段树上二分
- 线段树上二分
- 线段树上二分
具体细节这里不多说，可以看代码。
时间复杂度：$O(n \log n)$
代码
递交到P3369即可AC
const LL N = 1e5 + 10, Q = 1e5 + 10;
LL qc;
LL opt;
LL x;
struct Query{
LL opt;
LL x;
};
Query q[Q];
bs<LL> alls;
#define find(x) (lower_bound(all(alls), x) - alls.begin() + 1)
LL n;
#define lc ((x) * 2)
#define rc ((x) * 2 + 1)
#define mid ((l) + ((r) - (l)) / 2)
LL cnt[N * 4];
#define pushup(x) (cnt[x] = cnt[lc] + cnt[rc])
void updadd(LL x, LL l, LL r, LL mx, LL mv){
if(l == r){ cnt[x] += mv; return; }
if(mx <= mid) updadd(lc, l, mid, mx, mv);
else updadd(rc, mid + 1, r, mx, mv);
pushup(x);
}
LL getsum(LL x, LL l, LL r, LL ql, LL qr){
if(ql > qr) return 0;
if(ql <= l && r <= qr) return cnt[x];
LL ret = 0;
if(ql <= mid) ret += getsum(lc, l, mid, ql, qr);
if(mid + 1 <= qr) ret += getsum(rc, mid + 1, r, ql, qr);
return ret;
}
LL getrkx(LL x, LL l, LL r, LL qx){
if(l == r) return alls[l - 1];
if(cnt[lc] >= qx) return getrkx(lc, l, mid, qx);
else return getrkx(rc, mid + 1, r, qx - cnt[lc]);
}
#undef lc
#undef rc
#undef mid
void solve(){
rd(qc);
rep(i, 1, qc){
rd(opt), rd(x);
q[i] = {opt, x};
if(opt != 4) alls += x;
}
sort(all(alls));
alls.erase(unique(all(alls)), alls.end());
n = sz(alls);
rep(i, 1, qc){
LL opt = q[i].opt, &x = q[i].x;
if(opt != 4) x = find(x);
}
rep(i, 1, qc){
LL opt = q[i].opt, x = q[i].x;
if(opt == 1) updadd(1, 1, n, x, 1);
else if(opt == 2) updadd(1, 1, n, x, -1);
else if(opt == 3) printf("%lld\n", getsum(1, 1, n, 1, x - 1) + 1);
else if(opt == 4) printf("%lld\n", getrkx(1, 1, n, x));
else if(opt == 5) printf("%lld\n", getrkx(1, 1, n, getsum(1, 1, n, 1, x - 1)));
else printf("%lld\n", getrkx(1, 1, n, getsum(1, 1, n, 1, x) + 1));
}
}
动态开点权值线段树
不过，像P6136这样，强制在线了，怎么搞？很简单，加个动态开点即可。
就是动态开点可能不太好写，且常数、空间更大。
其他的没变，只是用的是“动态开点权值线段树”而已。
上联：可持久化带懒标记离线线段树
下联：有限状态乌姆尼克权值自动机
时间复杂度：$O(n \log n)$
代码
由于P6136过于卡空间，所以下面代码递交上去并不能AC，而是获得64分，所以仅供参考
const LL N = 1e5 + 10;
LL n, qc;
LL opt;
LL x;
#define lc (tlc[x])
#define rc (trc[x])
#define mid ((l) + ((r) - (l)) / 2)
LL cnt[N * 77];
LL tlc[N * 77], trc[N * 77];
LL ind;
#define pushup(x) (cnt[x] = cnt[lc] + cnt[rc])
LL newnode(){
ind++;
cnt[ind] = 0;
tlc[ind] = trc[ind] = 0;
return ind;
}
void updadd(LL &x, LL l, LL r, LL mx, LL mv){
if(x == 0) x = newnode();
if(l == r){ cnt[x] += mv; return; }
if(mx <= mid) updadd(lc, l, mid, mx, mv);
else updadd(rc, mid + 1, r, mx, mv);
pushup(x);
}
LL getsum(LL x, LL l, LL r, LL ql, LL qr){
if(ql > qr) return 0;
if(ql <= l && r <= qr) return cnt[x];
LL ret = 0;
if(ql <= mid && lc) ret += getsum(lc, l, mid, ql, qr);
if(mid + 1 <= qr && rc) ret += getsum(rc, mid + 1, r, ql, qr);
return ret;
}
LL getrkx(LL x, LL l, LL r, LL qx){
if(l == r) return l;
if(cnt[lc] >= qx) return getrkx(lc, l, mid, qx);
else return getrkx(rc, mid + 1, r, qx - cnt[lc]);
}
#undef lc
#undef rc
#undef mid
LL ans;
LL lans;
void solve(){
rd(n), rd(qc);
LL rt = 0;
cir(n){
rd(x);
updadd(rt, 0, (1 << 30) - 1, x, 1);
}
rep(i, 1, qc){
rd(opt), rd(x);
x ^= lans;
if(opt == 1) updadd(rt, 0, (1 << 30) - 1, x, 1);
else if(opt == 2) updadd(rt, 0, (1 << 30) - 1, x, -1);
else if(opt == 3) ans ^= (lans = getsum(rt, 0, (1 << 30) - 1, 1, x - 1) + 1 );
else if(opt == 4) ans ^= (lans = getrkx(rt, 0, (1 << 30) - 1, x) );
else if(opt == 5) ans ^= (lans = getrkx(rt, 0, (1 << 30) - 1, getsum(rt, 0, (1 << 30) - 1, 1, x - 1)));
else ans ^= (lans = getrkx(rt, 0, (1 << 30) - 1, getsum(rt, 0, (1 << 30) - 1, 1, x) + 1));
}
printf("%lld\n", ans);
}
二叉搜索树
有人问，既然这题标题是“平衡树”，这题怎么修改，才能让这题没法用线段树解决？
其实非常简单，这题是对数字做维护，我们改成维护pair、double、高精度整数，就无法用线段树解决，或者复杂度炸裂。
这时候，我们就要引入一个新算法——二叉搜索树（BST）了。
概览
正如简介中所说，BST是个左 $<$ 中 $<$ 右（指权值）结构的二叉树。
而这样的结构，就是为了方便插入和删除而设的。
初始化
如果给你一个序列，通过合理的方式，可以让BST的深度达到 $O(\log n)$ 级别。
其实现方式很简单，把这个序列从小到大排序，每次选择中间的元素 $\text{mid}$ 作为根，把比 $\text{mid}$ 小的作为左子树，大的作为右子树。
这样就是一个“类线段树结构”，树高一定是 $O(\log n)$ 的。
插入节点
接下来考虑插入。
其实很简单，如果当前节点权值比插入权值大，就递归左儿子，否则递归右儿子。
如果没有，则新建并退出函数。
删除节点
然后考虑删除。
如果删除节点 $x$ 是叶子节点，那么可以直接删除。
否则，如果直接删除 $x$ 的话，就会导致整棵树分裂。
为了防止分裂，我们必须找一个节点出来，来代替节点 $x$，这样就可以直接删除 $x$ 点了。
为了保证BST的性质仍然满足，我们可以找到节点 $x$ 左子树中权值最大的那个，或者右子树中权值最小的。
找到这个点的话很简单，可以直接暴力。
由于BST要求左子树内的所有权值 $<$ 右子树内的所有权值，所以我们可以贪心。
递归过程中，无脑一直往左/右儿子走，如果都没有则返回。
然后，我们把这个节点和 $x$ 交换，并删除此时的 $x$ 点即可。
其他四种操作
类似于线段树上二分。
复杂度证明
时间复杂度：$O(?)$
看见那个“$?$”就说明我们得证明一下复杂度才能定结论。
可以发现，无论是删除、查询排名、查询前驱后继，这个复杂度其实都是和树高有关的。
而且，似乎插入对树高没什么影响啊，直接 $O(n \log n)$，用啥平衡树。
但是，这种做法复杂度并不是 $O(n \log n)$。
我们考虑一个极限数据。
我们依次插入 $1$、$2$、$3$、$4$、$\dots$、$5 \times 10^4$，这样就会让树高达到 $5 \times 10^4$ 而不是理想的 $\log n$。
这样的话，只要我们 $5 \times 10^4$ 次操作里，每次都查询一下 $5 \times 10^4$（最大数）的前驱，或者 $1$（最小数）的后继。
那么，复杂度就会达到 $O \left( \left( 5 \times 10^4 \right)^2 \right)$，爆炸。
所以我们考虑优化。
定期重构
其实上面的简介里也剧透了一点，就是我们考虑定期重构。
有一种算法叫“替罪羊树”，就是用定期重构来实现定期重构的平衡树，所以定期重构又被我称为“替罪羊树思想”。
而且，定期重构一般是每 $\sqrt n$ 次变化重构一次。
但这题里，只有插入操作会让树高变高，所以我们只要每加入 $\sqrt n$ 个数进行重构即可。
重构就是上面说的“初始化操作”，复杂度是 $O(n)$ 的。
所以总复杂度是 $O(n \sqrt n)$，因为瓶颈在于重构而不是查询。
这下复杂度就是大概率能接受的了。
代码
做法假了，因为删除操作里，顶替的那个点不一定为叶子节点，目前还没有解决该bug的思路
Treap
但这个复杂度还不够优，我们得把它优化成 $O(n \log n)$。
不过我们已经无法在算法上优化了，我们得换一种做法。
我们考虑Treap。
概览
其实Treap就是BST的扩展版。
BST是单单维护权值，但Treap还要维护一个“优先级”。
这个优先级是随机的，这也是它树高的保证。（这个证明过于复杂难懂，这里就不说了）
并且，在简介里也说了，优先级是满足小/大根堆性质的。
正是因为这一点，Treap的结构才是唯一的。（这个容易证明，随便找一个构造方式你就知道为啥了）
旋转
（最头疼的地方来了）
不过我们发现，不像BST，Treap的插入并不一定找到一个插入的地方。
所以，我们得尝试变化一下结构。
变化结构的方式被称为“旋转”
传入参数是一个 $x$，我们尝试把 $x$ 平移到 $x$ 的父亲的父亲位置。
这里的“平移”可以这么理解，我们设 $fa$ 为 $x$ 的父亲，那么：
- 如果 $x$ 是 $fa$ 的左儿子，则旋转后 $fa$ 要作为 $x$ 的右儿子。
- 如果 $x$ 是 $fa$ 的右儿子，则旋转后 $fa$ 要作为 $x$ 的左儿子。
但这个旋转也不那么简单。
因为 $x$ 的两个儿子的子树，还有 $fa$ 的某个子树，其排列位置可能会改变。
具体而言，它们会这么变化：
这种变化方式可以用代码实现：
void rotate(LL x){
if(fa(x) == rt) rt = x; //根节点特判
LL y = fa(x), z = fa(y), p = sp(x); //x的父亲、x的祖父、x是哪个儿子
sons(y, p) = sons(x, !p), sons(x, !p) = y, fa(sons(y, p)) = y; //交换子树
fa(x) = fa(y), fa(y) = x; //更换父亲节点
pushup(x), pushup(y); //pushup
if(z){ //如果x的祖父存在
sons(z, rc(z) == y) = x; //则变化其的儿子节点为x
pushup(z); //然后重新pushup
}
}
注：
上面图里有两个操作，“左旋（Left Rotation）”和“右旋（Left Rotation）”。
但这里只写了一个函数，有人问这个函数实现的是什么旋？其实这个函数其实既实现了左旋，又实现了右旋。
而这一点怎么理解呢？可以发现，用哪种旋法，只取决于这个点是左还是右儿子。
如果是左儿子，那么就得用右旋，否则用左旋。
所以上面代码既实现了左旋（节点 $x$ 为右儿子），也实现了右旋（节点 $x$ 为左儿子）。
在Splay里，会对“旋转”做升级（添加了一个splay操作，但rotate操作没变），这时候会更头疼。
附：
Treap要维护的信息：
struct Node{ LL val; //权值 LL pri; //优先级 LL sz; //子树大小 LL fath; //父亲节点 LL sons[2]; //两个儿子 };Treap的
#define有：#define val(x) (a[x].val) #define pri(x) (a[x].pri) #define sz(x) (a[x].sz) #define fa(x) (a[x].fath) #define sons(x, p) (a[x].sons[p]) #define lc(x) sons(x, 0) #define rc(x) sons(x, 1) #define sp(x) (rc(fa(x)) == x) //x的在哪个儿子上 #define pushup(x) (sz(x) = sz(lc(x)) + sz(rc(x))) //pushup操作这些信息只是为了方便理解代码，不用全抄。
插入
在插入操作里，我们先忽略优先级，按BST的性质找到插入点。
然后，从该点遍历到根。
遍历到某个点的时候，如果该点的优先级比它的父亲的要小（假设要求优先级满足大根堆性质）。
那么，我们就得调用旋转操作，把当前点旋上去。
由于Treap的结构唯一且期望高度为 $O(\log n)$，并且最后整棵树必然满足Treap性质。
所以，插入操作不会对树高产生影响。
删除
删除的话，如果是叶子节点那么直接删。
否则，我们找到删除节点编号，并从这个地方开始往下递归。
每次我们看当前点的两个子节点，选择优先级较大的点，将其旋转到父亲那里，并递归到这个子节点。
这样不断旋转，就会使得删除节点为叶子，就直接删即可。
最后树结构满足Treap性质，所以不会对树高产生影响。
其他四种操作
可参考BST。
复杂度
复杂度还是与树高有关。
由于优先级随机，期望树高是 $O(\log n)$，所以复杂度就是 $O(q \log n)$。
代码
不合并相同权值版：
递交到P6136即可AC
const LL N = 1e5 + 10, Q = 1e6 + 10;
random_device rand_seed;
mt19937_64 _rand(time(0) ^ clock() ^ rand_seed());
#define random(l, r) (_rand() % ((LL)(r) - (LL)(l) + 1) + (LL)(l))
LL n, qc;
LL opt;
LL x;
struct Node{
LL val; //权值
LL pri; //优先级
LL sz; //子树大小
LL ma; //子树内权值最大值
LL fath; //父亲节点
LL sons[2]; //两个儿子
};
#define val(x) (a[x].val)
#define pri(x) (a[x].pri)
#define sz(x) (a[x].sz)
#define ma(x) (a[x].ma)
#define fa(x) (a[x].fath)
#define sons(x, p) (a[x].sons[p])
#define lc(x) sons(x, 0)
#define rc(x) sons(x, 1)
Node a[N + Q];
LL ind;
LL rt; //由于涉及交换，所以这里要专门存储根节点编号
bool flag = false; //根节点是否被删掉
#define sp(x) (rc(fa(x)) == x)
#define pushup(x) (sz(x) = sz(lc(x)) + 1 + sz(rc(x)), ma(x) = max({ma(lc(x)), val(x), ma(rc(x))}))
void rotate(LL x){
if(fa(x) == rt) rt = x; //如果是把某个根节点的儿子rotate上去，则这个儿子要作为新的根节点
LL y = fa(x), z = fa(y), p = sp(x); //x的父亲、x的祖父、x是哪个儿子
sons(y, p) = sons(x, !p), sons(x, !p) = y, fa(sons(y, p)) = y; //交换子树
fa(x) = fa(y), fa(y) = x; //更换父亲节点
pushup(y), pushup(x) /* 这里要注意顺序，先对y点做pushup，然后才对其父亲x做pushup，这样才能让信息传达正确 */; //pushup
if(z){ //如果x的祖父存在
sons(z, rc(z) == y) = x; //则变化其的儿子节点为x
pushup(z); //然后重新pushup
}
}
LL newnode(LL v, LL fa){
ind++;
val(ind) = v;
pri(ind) = random(1, 1e18);
sz(ind) = 1;
ma(ind) = v;
fa(ind) = fa;
lc(ind) = rc(ind) = 0;
return ind;
}
void add(LL x){
if(ind == 0){ rt = newnode(x, 0); return; }
if(flag){ ind = 0, flag = false, rt = newnode(x, 0); return; }
LL p = rt, ip = 0;
while(true){
LL &to = (x <= val(p) ? lc(p) : rc(p));
if(to == 0){ ip = to = newnode(x, p); break; }
else p = to;
}
while(ip > 1)
if(pri(ip) < /* 如果要求pri为大根堆，这里应该写>，但代码里要求pri为小根堆 */ pri(fa(ip)))
rotate(ip); //这里rotate之后，底下不用把ip再设成fa(ip)，因为rotate已经把fa值更新了
else
break;
while(ip) pushup(ip), ip = fa(ip);
}
void delnode(LL x){
if(x == rt) flag = true;
val(x) = 0;
pri(x) = 0;
sz(x) = 0;
ma(x) = 0;
sons(fa(x), sp(x)) = 0;
fa(x) = 0;
lc(x) = rc(x) = 0;
}
void del(LL x){
LL p = rt;
while(true){
LL lc = lc(p), rc = rc(p);
if(x == val(p)) break;
else if(x < val(p)) p = lc;
else p = rc;
}
if(lc(p) == 0 && rc(p) == 0){
LL t = fa(p);
delnode(p);
p = t;
while(p) pushup(p), p = fa(p); //这里要记得pushup
//这里要return，因为如果涉及到这种情况，那么执行完while循环，p一定为0，这时候下面代码就很可能会死循环
//具体原因不详，但能大概确定是0有儿子导致的死循环
return;
}
while(true){
LL lc = lc(p), rc = rc(p);
//还是，下面p不用专门设成lc或rc
if(lc == 0 && rc == 0) break;
else if(rc == 0) rotate(lc);
else if(lc == 0) rotate(rc);
else{
if(pri(lc) >= pri(rc)) rotate(lc);
else rotate(rc);
}
}
LL t = fa(p);
delnode(p);
p = t;
while(p) pushup(p), p = fa(p); //这里要记得pushup
}
LL getsm(LL x){
if(ind == 0 || flag) return 0; //此处要判断树为空的情况，这时候要及时返回0
LL p = rt;
LL ret = 0;
while(true){
if(val(p) <= x) ret++;
LL lc = lc(p), rc = rc(p);
if(lc == 0 && rc == 0) break;
else if(rc == 0) p = lc;
else if(lc == 0) p = rc;
else{
if(x < ma(lc)) p = lc;
else ret += sz(lc), p = rc;
}
}
return ret;
}
LL getrk(LL x){
LL p = rt;
while(true){
LL lc = lc(p), rc = rc(p);
if(lc == 0 && rc == 0){
if(x == 1) return val(p);
else return -1;
}else if(rc == 0){
if(x == sz(lc) + 1) return val(p);
else if(1 <= x && x <= sz(lc)) p = lc;
else return -2;
}else if(lc == 0){
if(x == 1) return val(p);
else if(2 <= x && x <= sz(rc) + 1) x--, p = rc;
else return -3;
}else{
if(x <= sz(lc)) p = lc;
else if(x == sz(lc) + 1) return val(p);
else x -= sz(lc) + 1, p = rc;
}
}
return -4;
}
LL ans;
LL lans;
void solve(){
rd(n), rd(qc);
rep(i, 1, n){
rd(x);
add(x);
}
rep(i, 1, qc){
rd(opt), rd(x);
x ^= lans;
if(opt == 1) add(x);
else if(opt == 2) del(x);
else if(opt == 3) ans ^= (lans = getsm(x - 1) + 1 );
else if(opt == 4) ans ^= (lans = getrk(x) );
else if(opt == 5) ans ^= (lans = getrk(getsm(x - 1)));
else ans ^= (lans = getrk(getsm(x) + 1));
}
printf("%lld\n", ans);
}
合并相同权值版：
递交到P6136即可AC
const LL N = 1e5 + 10, Q = 1e6 + 10;
random_device rand_seed;
mt19937_64 _rand(time(0) ^ clock() ^ rand_seed());
#define random(l, r) (_rand() % ((LL)(r) - (LL)(l) + 1) + (LL)(l))
LL n, qc;
LL opt;
LL x;
struct Node{
LL val; //权值
LL cnt; //权值出现次数（这也就意味着我们把相同的权值都合并到一个点上了）
LL pri; //优先级
LL sz; //子树大小
LL ma; //子树内权值最大值
LL fath; //父亲节点
LL sons[2]; //两个儿子
};
#define val(x) (a[x].val)
#define vcnt(x) (a[x].cnt)
#define pri(x) (a[x].pri)
#define sz(x) (a[x].sz)
#define ma(x) (a[x].ma)
#define fa(x) (a[x].fath)
#define sons(x, p) (a[x].sons[p])
#define lc(x) sons(x, 0)
#define rc(x) sons(x, 1)
Node a[N + Q];
LL ind;
LL rt; //由于涉及交换，所以这里要专门存储根节点编号
bool flag = false; //根节点是否被删掉
#define sp(x) (rc(fa(x)) == x)
#define pushup(x) (sz(x) = sz(lc(x)) + vcnt(x) + sz(rc(x)), ma(x) = max({ma(lc(x)), val(x), ma(rc(x))}))
void rotate(LL x){
if(fa(x) == rt) rt = x; //如果是把某个根节点的儿子rotate上去，则这个儿子要作为新的根节点
LL y = fa(x), z = fa(y), p = sp(x); //x的父亲、x的祖父、x是哪个儿子
sons(y, p) = sons(x, !p), sons(x, !p) = y, fa(sons(y, p)) = y; //交换子树
fa(x) = fa(y), fa(y) = x; //更换父亲节点
pushup(y), pushup(x) /* 这里要注意顺序，先对y点做pushup，然后才对其父亲x做pushup，这样才能让信息传达正确 */; //pushup
if(z){ //如果x的祖父存在
sons(z, rc(z) == y) = x; //则变化其的儿子节点为x
pushup(z); //然后重新pushup
}
}
LL newnode(LL v, LL fa){
ind++;
val(ind) = v;
vcnt(ind) = 1;
pri(ind) = random(1, 1e18);
sz(ind) = 1;
ma(ind) = v;
fa(ind) = fa;
lc(ind) = rc(ind) = 0;
return ind;
}
void add(LL x){
if(ind == 0){ rt = newnode(x, 0); return; }
if(flag){ ind = 0, flag = false, rt = newnode(x, 0); return; }
LL p = rt, ip = 0;
while(true){
if(x == val(p)){
vcnt(p)++;
while(p) sz(p)++, p = fa(p); //这里要把sz值一并变化，并且不止变化p
return;
}
LL &to = (x < val(p) ? lc(p) : rc(p));
if(to == 0){ ip = to = newnode(x, p); break; }
else p = to;
}
while(ip > 1)
if(pri(ip) < /* 如果要求pri为大根堆，这里应该写<，但代码里要求pri为小根堆 */ pri(fa(ip)))
rotate(ip); //这里rotate之后，底下不用把ip再设成fa(ip)，因为rotate已经把fa值更新了
else
break;
while(ip) pushup(ip), ip = fa(ip);
}
void delnode(LL x){
val(x) = 0;
vcnt(x) = 0;
pri(x) = 0;
sz(x) = 0;
ma(x) = 0;
sons(fa(x), sp(x)) = 0;
fa(x) = 0;
lc(x) = rc(x) = 0;
}
void del(LL x){
LL p = rt;
while(true){
LL lc = lc(p), rc = rc(p);
if(x == val(p)) break;
else if(x < val(p)) p = lc;
else p = rc;
}
if(vcnt(p) > 1){
vcnt(p)--;
while(p) sz(p)--, p = fa(p); //这里要把sz值一并变化，并且不止变化p
return;
}
if(lc(p) == 0 && rc(p) == 0){
LL t = fa(p);
delnode(p);
p = t;
while(p) pushup(p), p = fa(p); //这里要记得pushup
//这里要return，因为如果涉及到这种情况，那么执行完while循环，p一定为0，这时候下面代码就很可能会死循环
//具体原因不详，但能大概确定是0有儿子导致的死循环
return;
}
while(true){
LL lc = lc(p), rc = rc(p);
//还是，下面p不用专门设成lc或rc
if(lc == 0 && rc == 0) break;
else if(rc == 0) rotate(lc);
else if(lc == 0) rotate(rc);
else{
if(pri(lc) >= pri(rc)) rotate(lc);
else rotate(rc);
}
}
LL t = fa(p);
delnode(p);
p = t;
while(p) pushup(p), p = fa(p); //这里要记得pushup
}
LL getsm(LL x){
if(ind == 0 || flag) return 0; //此处要判断树为空的情况，这时候要及时返回0
LL p = rt;
LL ret = 0;
while(true){
if(val(p) <= x) ret += vcnt(p);
LL lc = lc(p), rc = rc(p);
if(lc == 0 && rc == 0) break;
else if(rc == 0) p = lc;
else if(lc == 0) p = rc;
else{
if(x < ma(lc)) p = lc;
else ret += sz(lc), p = rc;
}
}
return ret;
}
LL getrk(LL x){
LL p = rt;
while(true){
LL lc = lc(p), rc = rc(p);
if(lc == 0 && rc == 0){
if(1 <= x && x <= vcnt(p)) return val(p);
else return -1;
}else if(rc == 0){
if(1 <= x && x <= sz(lc)) p = lc;
else if(sz(lc) + 1 <= x && x <= sz(lc) + vcnt(p)) return val(p);
else return -2;
}else if(lc == 0){
if(1 <= x && x <= vcnt(p)) return val(p);
else if(vcnt(p) + 1 <= x && x <= vcnt(p) + sz(rc)) x -= vcnt(p), p = rc;
else return -3;
}else{
if(1 <= x && x <= sz(lc)) p = lc;
else if(sz(lc) + 1 <= x && x <= sz(lc) + vcnt(p)) return val(p);
else x -= sz(lc) + vcnt(p), p = rc;
}
}
return -4;
}
LL ans;
LL lans;
void solve(){
rd(n), rd(qc);
rep(i, 1, n){
rd(x);
add(x);
}
rep(i, 1, qc){
rd(opt), rd(x);
x ^= lans;
if(opt == 1) add(x);
else if(opt == 2) del(x);
else if(opt == 3) ans ^= (lans = getsm(x - 1) + 1 );
else if(opt == 4) ans ^= (lans = getrk(x) );
else if(opt == 5) ans ^= (lans = getrk(getsm(x - 1)));
else ans ^= (lans = getrk(getsm(x) + 1));
}
printf("%lld\n", ans);
}
Splay
不过如果出现更多种类的修改、查询呢？我们可以考虑Splay。
概览
接下来是Splay，其实Splay能解决所有Treap能解决的问题，同时还可以解决区间修改、翻转、查询问题。
不过其缺点上面也说了，非常难写、细节贼多、非常难理解、复杂度很难证明，不过这些缺点是因人而异的。
并且，在比赛里，能用权值线段树就用，不能用就用Treap，如果仍然不能用再用Splay。
因为Splay本身常数就不算小，并且有时候写挂一个小点可能连对拍都拍不出来。
旋转
上面剧透了一下，就是Splay里会对旋转做升级，这里说一下是如何升级的。
其实上面说的添加的splay操作，并不是什么很高深的操作，其原理就是把传入的那个点，一路旋转到根。
我们假设传入的点为 $x$ 号点，且设：
- $y$ 为 $x$ 的父亲
- $z$ 为 $x$ 的祖父，即 $y$ 的父亲
那么我们就考虑先通过若干次rotate操作，让 $x$ 在 $x$、$y$、$z$ 三点中深度最浅。
我们可以分两种情况：
- $x$ 和 $y$ 是一个儿子方向：
- $x$ 和 $y$ 不是一个儿子方向：
（图源网络，在这篇博客里）
不过前提 $z$ 是存在的。
这样，我们就可以写出splay操作的代码：
void splay(LL x){ //将一个点x旋转到根
//如果x和fa（x的父亲）的子节点关系一致，则旋转fa后旋转x
//否则，旋转两次x
for(LL fa = fa(x);fa;rotate(x) /* rotate完后不用把x赋值为其父亲 */, fa = fa(x))
if(fa(fa))
rotate(sp(x) == sp(fa) ? fa : x);
rt = x;
}
（提前剧透一下，在底下splay操作的实现会变）
插入
如果树为空，直接新建节点加入树中即可。
否则我们仿照Treap的“合并相同权值版本”代码实现即可。
不过注意，在找到加入位置后，一定要把插入的位置旋转到根。
放代码：
void add(LL x){ //添加数x（且将数x旋转到根）
//特判树为空
if(rt == 0){
ind = 0;
rt = newnode(x, 0);
return;
}
//找到添加点
LL p = rt;
while(true){
//如果有相同的权值，直接cnt++即可
if(val(p) == x){
cnt(p)++;
pushup(fa(p));
splay(p);
return;
}
//否则找到去哪个儿子
LL &to = sons(p, x > /* 这里是大于 */ val(p));
//如果该儿子没有
if(to == 0){
//则新增
to = newnode(x, p);
pushup(p);
splay(to);
return;
//否则走到该儿子
}else p = to;
}
exit(1);
}
查询x的排名
仿照Treap的实现即可。
这里也要把我们找到的点旋转到根。
有人问为啥每次都要旋转，有两个原因：
- 有时候旋转到根有别用。
- 旋转操作是复杂度的保证，这也就意味着旋转操作多多益善，少了可能会挂。
放代码：
LL getrnk(LL x){ //查询数x的排名（且将数x旋转到根）
LL p = rt;
LL ret = 0;
while(p)
//如果x比当前权值小，则说明答案都在左子树
if(x < val(p)) p = lc(p);
//否则就是整个左子树、当前节点，和部分右子树
else{
//将左子树整个累加
ret += sz(lc(p));
//如果找到了x所在节点
if(x == val(p)){
//则把该节点旋转到根
splay(p);
//此时的ret为比x小的元素个数，所以要加1后返回
return ret + 1;
}
//否则当前节点也在答案范围内
ret += cnt(p);
//去右儿子更新答案
p = rc(p);
}
exit(2);
}
查询排名为x的数
差不多的思路。
还是要旋转到根。
（剧透一下，看到底下就会发现，splay操作不能放到函数内实现了）
放代码：
LL getkth(LL x){ //查询第x名的数（且将该数旋转到根）
LL p = rt;
while(p)
//如果左儿子存在，且x比左儿子大小要小（或等于），则说明答案在左儿子内
if(lc(p) && x <= sz(lc(p))) p = lc(p);
//否则就在当前节点，或者右子树内
else{
//先假设在右子树内
x -= sz(lc(p)) + cnt(p);
//如果减之后比0小，则答案一定是当前节点
if(x <= 0){
//旋转到根
splay(p);
//返回
return val(p);
}
//否则，就在右子树内
p = rc(p);
}
exit(3);
}
查询x的前驱
先把 $x$ 插入，此时 $x$ 已经默认旋转到根了。
于是我们跳左儿子，然后不断跳右儿子即可。
找到位置之后，splay到根即可。
放代码：
LL getpre(LL x){ //查询数x的前驱节点编号（且将前驱旋转到根，保证在调用前x一定存在于树中，且是作为根出现）
//保证是根
LL p = rt;
//先向左（走到左儿子内）一下
p = lc(p);
//如果左儿子不存在，就说明无解
if(p == 0) exit(4);
//否则，无脑往右走（走到右儿子内）即可
while(rc(p)) p = rc(p);
//直到没有右儿子的时候，就旋转
splay(p);
//并返回p节点
return p;
}
查询x的后继
类似的，只不过是先跳右儿子，然后跳左儿子。
还是要旋转到根。
放代码：
LL getnxt(LL x){ //查询数x的后继节点编号（且将后继旋转到根，保证在调用前x一定存在于树中，且是作为根出现）
//保证是根
LL p = rt;
//先向右（走到右儿子内）一下
p = rc(p);
//如果右儿子不存在，就说明无解
if(p == 0) exit(5);
//否则，无脑往左走（走到左儿子内）即可
while(lc(p)) p = lc(p);
//直到没有左儿子的时候，就旋转
splay(p);
//并返回p节点
return p;
}
删除
删除操作最后讲，是因为删除涉及到上面的操作。
我们首先找到删除的数（假设为 $x$）所在位置，然后把这个位置旋转到根。
之后，如果我们发现 $x$ 出现过不止一次，就直接把出现次数自减即可。
否则，我们分类讨论：
- 如果此时的根（数 $x$）没有任何儿子：
- 那么就说明整个树内就只有一个点，直接删除即可。
- 如果只有左儿子：
- 直接把左儿子当根即可。
- 如果只有右儿子：
- 直接把右儿子当根即可。
- 如果左右儿子都有：
- 则我们找到数 $x$ 的前驱。
- 此时前驱就默认旋转到根了，且数 $x$ 是作为根节点的右儿子的。
- 并且根节点的右儿子（数 $x$）是没有左儿子的，显然。
- 于是我们把数 $x$ 的右儿子街道根节点上即可。
于是即可写出代码：
void del(LL x){ //删除数x
//找到删除位置
LL p = rt;
while(true){
if(p == 0) exit(6);
//找到了
if(val(p) == x) break;
//继续跳儿子
p = sons(p, x > /* 这里是大于 */ val(p));
}
//把删除位置旋转到根
splay(p);
//如果有多于一个权值为x的
if(cnt(rt) > 1){
//则直接cnt--即可
cnt(rt)--;
pushup(rt);
return;
}
//如果根没有左右儿子（整棵树就只有rt一个点）
if(lc(rt) == 0 && rc(rt) == 0){
delnode(rt);
//如果根只有左儿子
}else if(rc(rt) == 0){
//则拿左儿子作为根，并删除原根
LL t = rt;
rt = lc(rt);
fa(rt) = 0;
delnode(t);
//如果根只有右儿子
}else if(lc(rt) == 0){
//则拿右儿子作为根，并删除原根
LL t = rt;
rt = rc(rt);
fa(rt) = 0;
delnode(t);
//如果左右儿子都有
}else{
//则把此时根节点的前驱旋转到根
LL t = rt;
getpre(val(rt));
//把旧根删掉即可
//此时旧根t一定是新根rt的右儿子
//并且不可能存在权值在val(t)与val(rt)之间（不包括两端点val(t)和val(rt)的值）的节点
//这也就意味着此时t没有左儿子
//只用把右儿子连到新根上去即可
rc(rt) = rc(t);
fa(rc(rt)) = rt;
fa(t) = 0; //为了防止在delnode的时候把此时的根（t的父亲rt）的某个儿子清零，这里要把t的父亲指向0
delnode(t /* BBE++，原为rt */);
pushup(rt); //并更新此时rt的信息
}
}
复杂度
这个复杂度是可以证明的，其均摊复杂度为 $O(\log n)$，其中 $n$ 为节点数。
证明：
（暑假的时候补）
不过有时候少旋转了，可能会导致复杂度增加，所以建议比赛的时候（特别是OI赛制比赛）造几个边界数据看是否能过。
代码
递交到P3369即可AC
const LL Q = 1e5 + 10;
LL q;
LL opt, x;
struct Node{
//对于单点而言
LL val; //节点权值
LL cnt; //权值出现次数
//对于邻边而言
LL fa; //父亲节点
LL sons[2]; //两个儿子节点
//对于子树而言
LL sz; //子树大小
};
#define val(x) (a[x].val)
#define cnt(x) (a[x].cnt)
#define fa(x) (a[x].fa)
#define sons(x, p) (a[x].sons[p])
#define lc(x) sons(x, 0)
#define rc(x) sons(x, 1)
#define sz(x) (a[x].sz)
Node a[Q]; //所有节点的信息
LL ind; //目前编号到几了
LL rt; //根节点编号（由于有删除、旋转操作，所以根会不断变化）
#define sp(x) (rc(fa(x)) == x) //x是哪个儿子
#define pushup(x) (sz(x) = sz(lc(x)) + cnt(x) + sz(rc(x))) //上传信息
LL newnode(LL v, LL fa){ //新增一个权值为v、父亲节点为fa的点
ind++;
val(ind) = v;
cnt(ind) = 1;
fa(ind) = fa;
lc(ind) = rc(ind) = 0;
sz(ind) = 1;
return ind;
}
void delnode(LL x){ //删除节点x（如果x为根，则将根编号赋值为0）
if(x == rt) rt = 0;
val(x) = 0;
cnt(x) = 0;
sons(fa(x), sp(x)) = 0;
fa(x) = 0;
lc(x) = rc(x) = 0;
sz(x) = 0;
}
void rotate(LL x){ //旋转操作
LL y = fa(x), z = fa(y), p = sp(x);
sons(y, p) = sons(x, !p), sons(x, !p) = y, fa(sons(y, p)) = y;
fa(x) = fa(y), fa(y) = x;
pushup(y), pushup(x);
if(z){
sons(z, rc(z) == y) = x;
pushup(z);
}
}
void splay(LL x){ //将一个点x旋转到根
//如果x和fa（x的父亲）的子节点关系一致，则旋转fa后旋转x
//否则，旋转两次x
for(LL fa = fa(x);fa;rotate(x) /* rotate完后不用把x赋值为其父亲 */, fa = fa(x))
if(fa(fa))
rotate(sp(x) == sp(fa) ? fa : x);
rt = x;
}
void add(LL x){ //添加数x（且将数x旋转到根）
//特判树为空
if(rt == 0){
ind = 0;
rt = newnode(x, 0);
return;
}
//找到添加点
LL p = rt;
while(true){
//如果有相同的权值，直接cnt++即可
if(val(p) == x){
cnt(p)++;
pushup(fa(p));
splay(p);
return;
}
//否则找到去哪个儿子
LL &to = sons(p, x > /* 这里是大于 */ val(p));
//如果该儿子没有
if(to == 0){
//则新增
to = newnode(x, p);
pushup(p);
splay(to);
return;
//否则走到该儿子
}else p = to;
}
exit(1);
}
LL getrnk(LL x){ //查询数x的排名（且将数x旋转到根）
LL p = rt;
LL ret = 0;
while(p)
//如果x比当前权值小，则说明答案都在左子树
if(x < val(p)) p = lc(p);
//否则就是整个左子树、当前节点，和部分右子树
else{
//将左子树整个累加
ret += sz(lc(p));
//如果找到了x所在节点
if(x == val(p)){
//则把该节点旋转到根
splay(p);
//此时的ret为比x小的元素个数，所以要加1后返回
return ret + 1;
}
//否则当前节点也在答案范围内
ret += cnt(p);
//去右儿子更新答案
p = rc(p);
}
exit(2);
}
LL getkth(LL x){ //查询第x名的数（且将该数旋转到根）
LL p = rt;
while(p)
//如果左儿子存在，且x比左儿子大小要小（或等于），则说明答案在左儿子内
if(lc(p) && x <= sz(lc(p))) p = lc(p);
//否则就在当前节点，或者右子树内
else{
//先假设在右子树内
x -= sz(lc(p)) + cnt(p);
//如果减之后比0小，则答案一定是当前节点
if(x <= 0){
//旋转到根
splay(p);
//返回
return val(p);
}
//否则，就在右子树内
p = rc(p);
}
exit(3);
}
LL getpre(LL x){ //查询数x的前驱节点编号（且将前驱旋转到根，保证在调用前x一定存在于树中，且是作为根出现）
//保证是根
LL p = rt;
//先向左（走到左儿子内）一下
p = lc(p);
//如果左儿子不存在，就说明无解
if(p == 0) exit(4);
//否则，无脑往右走（走到右儿子内）即可
while(rc(p)) p = rc(p);
//直到没有右儿子的时候，就旋转
splay(p);
//并返回p节点
return p;
}
LL getnxt(LL x){ //查询数x的后继节点编号（且将后继旋转到根，保证在调用前x一定存在于树中，且是作为根出现）
//保证是根
LL p = rt;
//先向右（走到右儿子内）一下
p = rc(p);
//如果右儿子不存在，就说明无解
if(p == 0) exit(5);
//否则，无脑往左走（走到左儿子内）即可
while(lc(p)) p = lc(p);
//直到没有左儿子的时候，就旋转
splay(p);
//并返回p节点
return p;
}
void del(LL x){ //删除数x
//找到删除位置
LL p = rt;
while(true){
if(p == 0) exit(6);
//找到了
if(val(p) == x) break;
//继续跳儿子
p = sons(p, x > /* 这里是大于 */ val(p));
}
//把删除位置旋转到根
splay(p);
//如果有多于一个权值为x的
if(cnt(rt) > 1){
//则直接cnt--即可
cnt(rt)--;
pushup(rt);
return;
}
//如果根没有左右儿子（整棵树就只有rt一个点）
if(lc(rt) == 0 && rc(rt) == 0){
delnode(rt);
//如果根只有左儿子
}else if(rc(rt) == 0){
//则拿左儿子作为根，并删除原根
LL t = rt;
rt = lc(rt);
fa(rt) = 0;
delnode(t);
//如果根只有右儿子
}else if(lc(rt) == 0){
//则拿右儿子作为根，并删除原根
LL t = rt;
rt = rc(rt);
fa(rt) = 0;
delnode(t);
//如果左右儿子都有
}else{
//则把此时根节点的前驱旋转到根
LL t = rt;
getpre(val(rt));
//把旧根删掉即可
//此时旧根t一定是新根rt的右儿子
//并且不可能存在权值在val(t)与val(rt)之间（不包括两端点val(t)和val(rt)的值）的节点
//这也就意味着此时t没有左儿子
//只用把右儿子连到新根上去即可
rc(rt) = rc(t);
fa(rc(rt)) = rt;
fa(t) = 0; //为了防止在delnode的时候把此时的根（t的父亲rt）的某个儿子清零，这里要把t的父亲指向0
delnode(t /* BBE++，原为rt */);
pushup(rt); //并更新此时rt的信息
}
}
void solve(){
rd(q);
rep(i, 1, q){
rd(opt), rd(x);
if(opt == 1) add(x);
else if(opt == 2) del(x);
else if(opt == 3) printf("%lld\n", getrnk(x) ) ;
else if(opt == 4) printf("%lld\n", getkth(x) ) ;
else if(opt == 5) add(x), printf("%lld\n", val(getpre(x))), del(x);
else add(x), printf("%lld\n", val(getnxt(x))), del(x);
}
}
区间操作、查询
不过这还没完，上面说“Splay能解决更多种类的操作、查询”，而具体是哪些呢？其实就是对区间的操作。
比如，最经典的就是对一段区间做翻转。
此时，我们设操作区间为 $[l,r]$，我们就考虑把这段区间提取为一个子树。
一种可行的思路是，我们把 $l-1$ 旋转到根，把 $r+1$ 旋转到根的右儿子。
有人说，这一步直接把 $r+1$ 旋转到根，随后把 $l-1$ 旋转到根不就彳亍了吗？事实并非如此。
实测在绝大部分情况下，这样都不能正确的提取 $[l,r]$ 这段区间。
所以，我们只能变化一下splay操作：
void splay(LL x, LL tar = 0){ //tar表示旋转到哪个点为止
for(LL fa = fa(x);fa != tar;rotate(x), fa = fa(x))
if(fa(fa) != tar)
rotate(sp(x) == sp(fa) ? fa : x);
if(tar == 0) /* 只有在tar=0的时候根节点才会变化 */ rt = x;
}
具体调用可以看底下的代码。
于是，此时根节点的右儿子的左儿子，就是 $[l,r]$ 这段区间对应子树的根。
我们只要在这个根上打标记即可。
或者如果是询问，就访问其权值即可。
注意在引入标记后，必须要时刻记得pushdown。
代码
只有旋转：
递交到P3391即可AC
const LL Q = 1e5 + 10;
LL n, q;
LL l, r;
struct Node{
LL val;
LL fa;
LL sons[2];
LL sz;
bool rev;
};
#define val(x) (a[x].val)
#define fa(x) (a[x].fa)
#define sons(x, p) (a[x].sons[p])
#define lc(x) sons(x, 0)
#define rc(x) sons(x, 1)
#define sz(x) (a[x].sz)
#define rev(x) (a[x].rev)
Node a[Q];
LL ind;
LL rt;
#define sp(x) (rc(fa(x)) == x)
#define pushup(x) (sz(x) = sz(lc(x)) + 1 + sz(rc(x)))
LL newnode(LL v, LL fa){
ind++;
val(ind) = v;
fa(ind) = fa;
lc(ind) = rc(ind) = 0;
sz(ind) = 1;
rev(ind) = false;
return ind;
}
LL build(LL l, LL r, LL fa){
if(l > r) return 0;
LL mid = l + (r - l) / 2;
LL x = newnode(mid, fa);
lc(x) = build(l, mid - 1, x), rc(x) = build(mid + 1, r, x);
pushup(x);
return x;
}
#define lazy_rev(x) (swap(lc(x), rc(x)), rev(x) ^= 1)
void pushdown(LL x){
if(rev(x)){
lazy_rev(lc(x));
lazy_rev(rc(x));
rev(x) = false;
}
}
void rotate(LL x){
LL y = fa(x), z = fa(y), p = sp(x);
pushdown(z), pushdown(y), pushdown(x);
sons(y, p) = sons(x, !p), sons(x, !p) = y, fa(sons(y, p)) = y;
fa(x) = fa(y), fa(y) = x;
pushup(y), pushup(x);
if(z){
sons(z, rc(z) == y) = x;
pushup(z);
}
}
void splay(LL x, LL tar = 0){ //tar表示旋转到哪个点为止
for(LL fa = fa(x);fa != tar;rotate(x), fa = fa(x))
if(fa(fa) != tar)
rotate(sp(x) == sp(fa) ? fa : x);
if(tar == 0) /* 只有在tar=0的时候根节点才会变化 */ rt = x;
}
LL getkth(LL x){
LL p = rt;
while(p){
pushdown(p);
if(lc(p) && x <= sz(lc(p))) p = lc(p);
else{
x -= sz(lc(p)) + 1;
if(x <= 0) return p; //不用着急在这里splay，在主程序里有详细处理
p = rc(p);
}
}
exit(1);
}
void dfs(LL x){
if(x == 0) return;
pushdown(x);
dfs(lc(x));
if(1 <= val(x) && val(x) <= n) printf("%lld ", val(x));
dfs(rc(x));
}
void solve(){
rd(n), rd(q);
build(0, n + 1, 0);
rt = 1;
cir(q){
rd(l), rd(r);
LL vl = getkth((l - 1) + 1);
splay(vl);
LL vr = getkth((r + 1) + 1);
splay(vr, vl);
lazy_rev(lc(rc(rt)));
}
dfs(rt);
puts("");
}
旋转、区间加、区间查询最大值：（重写的，函数化了，会更加好看一些）
递交到P4146即可AC
const LL N = 5e4 + 10;
LL n, q;
LL opt;
LL l, r, v;
struct Node{
LL val;
LL fa;
LL sons[2];
LL sz;
LL ma;
LL add;
bool rev;
};
#define val(x) (a[x].val)
#define fa(x) (a[x].fa)
#define sons(x, p) (a[x].sons[p])
#define lc(x) sons(x, 0)
#define rc(x) sons(x, 1)
#define sz(x) (a[x].sz)
#define ma(x) (a[x].ma)
#define add(x) (a[x].add)
#define rev(x) (a[x].rev)
Node a[N];
LL ind;
LL rt;
#define sp(x) (rc(fa(x)) == x)
#define pushup(x) (sz(x) = sz(lc(x)) + 1 + sz(rc(x)), ma(x) = max({ma(lc(x)), val(x), ma(rc(x))}))
void rotate(LL x){
LL y = fa(x), z = fa(y), p = sp(x);
sons(y, p) = sons(x, !p), sons(x, !p) = y, fa(sons(y, p)) = y;
fa(x) = fa(y), fa(y) = x;
pushup(y), pushup(x);
if(z){
sons(z, rc(z) == y) = x;
pushup(z);
}
}
void splay(LL x, LL tar = 0){
for(LL fa = fa(x);fa != tar;rotate(x), fa = fa(x))
if(fa(fa) != tar)
rotate(sp(x) == sp(fa) ? fa : x);
if(tar == 0) rt = x;
}
LL newnode(LL v, LL fa){
ind++;
val(ind) = v;
fa(ind) = fa;
lc(ind) = rc(ind) = 0;
sz(ind) = 1;
ma(ind) = v;
add(ind) = 0;
rev(ind) = false;
return ind;
}
LL build(LL l, LL r, LL fa){
if(l > r) return 0;
LL mid = l + (r - l) / 2;
LL cur = newnode(0, fa);
lc(cur) = build(l, mid - 1, cur);
rc(cur) = build(mid + 1, r, cur);
pushup(cur);
return cur;
}
void upd_lazy(LL x, LL add, bool rev){
if(add){
val(x) += add;
ma(x) += add;
add(x) += add;
}
if(rev){
swap(lc(x), rc(x));
rev(x) ^= rev;
}
}
void pushdown(LL x){
upd_lazy(lc(x), add(x), rev(x));
upd_lazy(rc(x), add(x), rev(x));
add(x) = 0, rev(x) = false;
}
LL getkth(LL x){
LL p = rt;
while(p){
pushdown(p);
if(lc(p) && x <= sz(lc(p))) p = lc(p);
else{
x -= sz(lc(p)) + 1;
if(x <= 0) return p;
p = rc(p);
}
}
exit(1);
}
LL lock_range(LL l, LL r){
LL xl = getkth((l - 1) + 1);
splay(xl);
LL xr = getkth((r + 1) + 1);
splay(xr, xl);
return lc(rc(rt));
}
void add_range(LL l, LL r, LL v){
upd_lazy(lock_range(l, r), v, false);
}
void rev_range(LL l, LL r){
upd_lazy(lock_range(l, r), 0, true);
}
LL max_range(LL l, LL r){
return ma(lock_range(l, r));
}
void solve(){
rd(n), rd(q);
ma(0) = -INF; //这里要把0节点的ma值设为-INF，防止权值为负，且某个儿子不存在（为0）的情况
build(0, n + 1, 0);
rt = 1;
cir(q){
rd(opt);
if(opt == 1) rd(l), rd(r), rd(v), add_range(l, r, v);
else if(opt == 2) rd(l), rd(r), rev_range(l, r);
else rd(l), rd(r), printf("%lld\n", max_range(l, r));
}
}