也只有我这种蒟蒻会现在才学平衡树吧……
本博客参考：PoPoQQQ 和 nzhtl1477 的课件；do_while_true, hzwer, 皎月半洒花 和 yybyyb 的代码启发
其实“参考”也就是我本人在学习时使用的资料。
前置 – 二叉搜索树（BST）
模板题：Luogu5076
关键性质：一个节点 $x$ 左子树所有点的关键字都比 $x$ 的关键字小，右子树所有点的关键字都比 $x$ 的关键字大。
支持：查询 $x$ 数的排名，查询排名为 $x$ 的数（$k$ 大值），求 $x$ 的前驱/后继，插入 $x$。
缺陷：按从小到大顺序插入值，复杂度会退化；不容易实现删除操作。
二叉搜索树（Binary Search Tree，以下简称 BST）的缺陷决定了这个算法必须被优化或取代，但是，由于平衡树的许多操作是与二叉平衡树相通（甚至相同）的，所以学习二叉平衡树非常有必要。
下面给出 BST 的的基本构造：
struct node{
int val,w,ls,rs,siz;//分别代表：关键字，关键字出现次数，左/右儿子，以该点为根的子树的大小（简称节点大小/子树大小）
}tree[N];
由于一个值可能会出现多次，如果分成多个点会造成不必要的麻烦，因为我们用 $w$ 记录同一个值的出现次数，用一个点记录下来。
由于 BST 比较容易理解，这里不再过度阐述，结合代码来简单阐述每一种操作。
插入
inline void insert(int v,int x){
tree[x].siz++;//大小加 1
if(tree[x].val==v){//要插入的这个值已存在并且找到，直接 w++
tree[x].w++;
return;
}
if(tree[x].val>v){//要插入的值较小，往左儿子走
if(tree[x].ls!=0) insert(v,tree[x].ls);
else{//没有左儿子，创建一个新点
tree[++cnt].val=v;
tree[cnt].siz=tree[cnt].w=1;
tree[x].ls=cnt;
}
}
else{//往右儿子走
if(tree[x].rs!=0) insert(v,tree[x].rs);
else{//同上
tree[++cnt].val=v;
tree[cnt].siz=tree[cnt].w=1;
tree[x].rs=cnt;
}
}
}
特别的，如果插入数时 BST 尚是空的，需要特判一下，然后执行以下代码即可：
tree[++cnt].val=x;
tree[cnt].siz=tree[cnt].w=1;
查询数 $x$ 的排名
inline int queryrk(int v,int x){
if(x==0) return 0;//找到尽头，返回 0，不可省略
if(tree[x].val==v) return tree[tree[x].ls].siz;//找到这个数，返回左儿子的大小
if(v<tree[x].val) return queryrk(v,tree[x].ls);//小于当前位置，向左儿子走
return tree[tree[x].ls].siz+tree[x].w+queryrk(v,tree[x].rs);//向右儿子走的同时，左儿子以及当前位置均比查询的数小，因此全部需要纳入答案中
}
注意，这里找到的排名实际为排名 $-1$ 的值（结合代码自行理解），所以如果要输出排名，代码应该为 printf("%d\n",queryrk(x,1)+1);
查询排名为 $x$ 的数（求 $k$ 大值）
inline int querynum(int rk,int x){
if(x==0) return 0;//找到尽头，返回 0，若必然找得到，可省略
if(tree[tree[x].ls].siz>=rk) return querynum(rk,tree[x].ls);
if(tree[tree[x].ls].siz+tree[x].w>=rk) return tree[x].val;
return querynum(rk-tree[tree[x].ls].siz-tree[x].w ,tree[x].rs);//上边两行都不满足，则相当于查询右儿子中排名为 rk-tree[tree[x].ls].siz-tree[x].w 的数
}
求 $x$ 的前驱/后继
前驱定义为小于 $x$，且最大的数；后继定义为大于 $x$，且最小的数。
inline int queryfr(int v,int ans,int x){//查询前驱
if(tree[x].val>=v){//当前位置不小于 x,去左子树找找有没有小于的
if(!tree[x].ls) return ans;//没有左子树，返回当前找到的合法的最大值
return queryfr(v,ans,tree[x].ls);
}
else{//当前位置小于 x，是合法的
if(!tree[x].rs) return tree[x].val;//没有右儿子，由于当前位置的左儿子一定小于当前位置，所以既然当前位置合法，就一定是当前位置的值
return queryfr(v,tree[x].val,tree[x].rs);//有右儿子，找找右儿子里有没有更大的合法的数
}
}
inline int queryne(int v,int ans,int x){//查询后继
if(tree[x].val<=v){//前驱的逆运算，原理类似，不再重复阐述
if(!tree[x].rs) return ans;
return queryne(v,ans,tree[x].rs);
}
else{
if(!tree[x].ls) return tree[x].val;
return queryne(v,tree[x].val,tree[x].ls);
}
}
至此，二叉搜索树的基本内容就结束了，在此基础上进行优化，也就来到了平衡树的内容。
平衡树的基本定义：利用旋转操作通过一些手段保证 BST 的复杂度不会退化的 BST 结构。
同时，平衡树也相对更能够支持删除操作。定义还告诉我们，平衡树的本质仍然是 BST，而旋转操作，也是平衡树学习的重点。
在 OI 中最常用的平衡树是 Treap 和 Splay，本文也仅仅对这两种平衡树进行说明（实际上我也就学了这两种平衡树ovo）。
Treap
tree（树）+heap（堆）=treap
顾名思义，treap 就是利用堆的性质来维护平衡的一种平衡树。核心思想就是：给每个点随机分配一个权值，使 treap 同时满足堆性质和二叉搜索树性质，这样可以使得树高期望保证在 $O(\log n)$，容易知道，treap 除了 BST 需要维护的信息以外，还需要额外维护一个堆随机值。
具体地说：
设每个节点的关键字是 $key$，随机权值是 $rnd$。
- 如果 $v$ 是 $u$ 的左儿子，则 $key_v < key_u$；
- 如果 $v$ 是 $u$ 的右儿子，则 $key_v > key_u$；
- 如果 $v$ 是 $u$ 的子节点，则 $rnd_u > rnd_v$。
要维护的信息具体如下：
struct node{
int ls,rs,w,siz,val,rnd;//rnd 为随机权值
}tr[N];
问题是如何使其同时满足堆性质和二叉搜索树性质呢？接着就是平衡树的核心——旋转操作。
旋转
旋转分为单旋和双旋，在 treap 中，只需要用到单旋（双旋会在 Splay 中阐述）。
单旋中又包含左旋和右旋，两者是互逆的。
用文字阐述就是：
左旋：将右儿子提到当前节点，自己作为右儿子的左儿子，右儿子原来的左儿子变成自己新的右儿子
右旋：将左儿子提到当前节点，自己作为左儿子的右儿子，左儿子原来的右儿子变成自己新的左儿子
为什么旋转操作非常重要？因为旋转有一个绝妙的性质——旋转后的二叉树仍满足二叉搜索树的条件。因此我们可以利用旋转操作来使 treap 满足堆性质，同时不破坏 BST 的性质。
旋转操作的代码如下：
inline void update(int x){//更新子树大小
tr[x].siz=tr[tr[x].ls].siz+tr[tr[x].rs].siz+tr[x].w;
}
inline void rturn(int &x){//右旋
int t=tr[x].ls;tr[x].ls=tr[t].rs;tr[t].rs=x;
tr[t].siz=tr[x].siz;update(x);x=t;
}
inline void lturn(int &x){//左旋
int t=tr[x].rs;tr[x].rs=tr[t].ls;tr[t].ls=x;
tr[t].siz=tr[x].siz;update(x);x=t;
}//x 一定要加 &，这样可以在更改 x 的值时同时修改之前的 ls/rs，结合插入/删除操作理解
treap 查询排名/$k$ 大值/前驱/后继的方法与 BST 完全相同，不再阐述，将会在文末贴出完整代码。
插入
treap 的插入操作与 BST 的差异保证了其复杂度不会退化，即：像 BST 那样插入，回溯时通过旋转来调整，使其满足堆性质。
inline void insert(int &x,int v){//&x 理由同上
if(x==0){//找到了一个尚无的节点，插入
cnt++;x=cnt;
tr[x].siz=tr[x].w=1;
tr[x].val=v;tr[x].rnd=rand();
return;
}
tr[x].siz++;
if(tr[x].val==v){
tr[x].w++;
return;
}
if(v>tr[x].val){
insert(tr[x].rs,v);
if(tr[tr[x].rs].rnd<tr[x].rnd) lturn(x);//插入完回溯的时候，需要看看需不需要旋转以满足堆性质，这里是以小根堆为例的，大根堆也可以
}
else{
insert(tr[x].ls,v);
if(tr[tr[x].ls].rnd<tr[x].rnd) rturn(x);//同上
}
}
删除
删除操作在平衡树中尤为重要。首先先用 BST 的方式找到要删除的数所在的节点（以下称为“当前节点”），然后：
- 若当前节点数值的出现次数大于 $1$ ，则将数值出现次数减 $1$ 即可。
- 若当前节点数值的出现次数等于 $1$ :
- 若当前节点没有左儿子与右儿子，则直接删除该节点；
- 若当前节点只有左儿子/右儿子，则用左儿子/右儿子替代该节点；
- 若当前节点有左儿子与右儿子，则不断旋转当前节点，并走到当前节点新的对应位置，直到当前节点只有左儿子/右儿子为止。
inline void del(int &x,int v){//同上
if(x==0) return;
if(tr[x].val==v){//找到了要删除的数
if(tr[x].w>1){//出现次数大于 1 ，直接 -1
tr[x].w--;tr[x].siz--;return;
}
if(tr[x].ls==0||tr[x].rs==0) x=tr[x].ls+tr[x].rs;//只有左儿子/右儿子，取而代之即可
else if(tr[tr[x].ls].rnd<tr[tr[x].rs].rnd){//左右儿子都有，开始不断旋转
rturn(x);//旋转时不仅需要满足 BST 性质，
del(x,v);//还需要满足堆性质（即判断 rnd 的大小再决定怎么旋转，
}//显然小堆顶情况下，需要让 rnd 小的旋转上来）
else{
lturn(x);
del(x,v);
}
}
else if(v>tr[x].val){//找要删除的数
tr[x].siz--;del(tr[x].rs,v);
}
else{
tr[x].siz--;del(tr[x].ls,v);
}
}
至此，我们实现了最基本的 treap ，完整代码会在文末代码部分贴出。
Splay
模板题：Luogu3391
Splay，又称文艺平衡树。Splay 对一个节点进行操作的时候通过一种方法把这个点旋转至根（即 splay 操作）,从而保证了平衡。Splay 的复杂度证明非常复杂（显然我也不会），故不作阐述。
为了简单说明在学会了 treap 情况下 Splay 的用途和不足，下面引用一段 nzhtl1477 的话：
Advantage:
Splay具有“自适应性”
大概就是说splay会根据操作的特点调整树结构，使得操作尽可能高效
可以去了解了解splay的动态最优性猜想，是个著名的open problem由于自适应性，splay不需要特殊的技巧就可以高效启发式合并，还可以高效实现LCT（STT）等动态树
Disadvantage:
可以通过势能分析证明splay的复杂度是均摊O( logn )的，也就是说splay在很多次操作中可能会有一次 $O( n )$ 复杂度的操作，而且这样的操作也很好构造，所以splay不适合做一些需要撤销操作/可持久化的题目（虽然可以通过随机旋转什么的方法来规避，但还是感觉很吃力）
自身常数比较大
单旋操作的 Splay 复杂度无法保证，因此我们需要通过双旋操作来保证其复杂度（同样不会证明）。
如果对证明非常感兴趣，可以看 delayyy 的课件：http://delayyy.blog.uoj.ac/blog/90
由于双旋（下文会阐述）中需要父亲/祖父的参与，因此我们除了 BST 中需要维护的以外，我们还需要维护每一个节点的父亲节点。
struct Splay_Tree{
int son[2],fa,cnt,val,siz;//son0=ls son1=rs
}tree[N];
Splay 的代码和 treap 不是同一天打的，打 Splay 的时候发现原先 ls,rs 的标法对打代码造成了非常大的麻烦（看下去就知道了），所以改用了主流的 son[2]
双旋
先上文字阐述：
讨论 $x$ 和父亲的关系与 $x$ 父亲和祖父的关系是否相同(换句话说 $x$-父亲-祖父是不是直的)
- $x$ 的父亲是根：旋转一次到根；
- $x$ 是父亲的左/右儿子且 $x$ 父亲是 $x$ 祖父的左/右儿子：先右/左旋祖父，再右/左旋父亲（下方第一张图）；
- $x$ 是父亲的左/右儿子但 $x$ 父亲是 $x$ 祖父的右/左儿子：先右/左旋父亲，再左/右旋祖父（下方第二张图）。
代码和 splay 操作一起讲。
splay 操作
为了阐述清晰，我胡乱规定该数据结构用 Splay 表示，该操作用 splay 操作表示（没有任何道理，纯粹是为了防止混淆）。
定义：将节点 $x$ 通过旋转操作旋转到根的位置。
接着直接结合代码来看。
inline void update(int u){//更新节点大小
tree[u].siz=tree[tree[u].son[0]].siz+tree[tree[u].son[1]].siz+tree[u].cnt;
}
inline bool check(int u){//判断左/右儿子，左儿子返回 0,右儿子返回 1
return tree[tree[u].fa].son[1]==u;
}
inline void rotate(int u){//将 u 旋转上去，这个定义和我写的 treap 略有不同
int fa=tree[u].fa;
int ffa=tree[fa].fa;
int k=check(u);
tree[ffa].son[check(fa)]=u;tree[u].fa=ffa;//各种更新父亲不要漏了
tree[fa].son[k]=tree[u].son[k^1];tree[tree[u].son[k^1]].fa=fa;
tree[u].son[k^1]=fa;tree[fa].fa=u;
update(fa);update(u);//先更新 fa ，理由显然
}
inline void splay(int u,int goal){//将节点 u 旋转到父亲为 goal 为止
while(tree[u].fa!=goal){//没到
int fa=tree[u].fa;
int ffa=tree[fa].fa;
if(ffa!=goal){//祖父不是目标，它就要被转
if(check(u)==check(fa)) rotate(fa);//判断先转父亲还是先转 u
else rotate(u);
}
rotate(u);//第二步肯定是转 u
}
if(!goal) root=u;
}
而这个操作也是我们保证 Splay 复杂度的关键，每对一个节点进行操作的时候我们都 splay 一下把该节点变成根，复杂度就得到了保证，代码与 BST 较为类似，就是多了一行 splay 操作，这里不再阐述插入/删除/查询等操作。
建树
阐述 treap 的时候，我们是对一个个值进行维护，而在 Splay 模板题中，我们需要对于一个区间进行维护，因此首先就需要对这一个区间建树（关键字就是在区间中的位置）。这部分比较简单，不多做阐述，略做修改也可以成为 treap 的建树方法。
inline int build(int l,int r,int fa){//简单递归建树
if(l>r) return 0;
int v=++cnt;
tree[v].fa=fa;
tree[v].cnt=1;
int mid=(l+r)>>1;
tree[v].val=a[mid];//权值就是 mid 的原始值
tree[v].son[0]=build(l,mid-1,v);
tree[v].son[1]=build(mid+1,r,v);
update(v);
return v;
}
容易知道，所得到的二叉树的中序遍历就是原序列（最终的中序遍历就是最终序列）。
原因：本模板题中，关键字实际上就是在当前序列中的序号，由于在 BST 中中序遍历会以关键字从小到大遍历，因而中序遍历得到的结果就是真实序列。
区间翻转
区间翻转就是模板题给我们要求，也是 treap 难以实现而 Splay 较容易实现的一项操作，是 Splay 的优势之一。
对于每次翻转区间 $[l,r]$，我们利用 Splay 的特性，运用 splay 操作，将 $l-1$ 旋转到根节点，再将 $r+1$ 旋转到根节点的右儿子，这样，$r+1$ 的左儿子代表的子树显然就是 $[l,r]$。
之后我们只需要给 $r+1$ 的左儿子打上一个翻转的 tag （即，交换左右儿子）并依次传递下去即可。容易发现，一层一层交换之后，二叉树的中序遍历就成功反过来了，也就是说成功完成了序列翻转。
inline void pushdown(int x){
if(tree[x].tag){
tree[tree[x].son[0]].tag^=1;
tree[tree[x].son[1]].tag^=1;
swap(tree[x].son[0],tree[x].son[1]);//交换左右儿子
tree[x].tag=0;
}
}
inline int query(int rk){//查询第 k 大的数的位置，由于权值为在序列中的序号，所以后第 k 大也就是在序列中的第 k 个数
int u=root;
pushdown(u);//一边找一边要 pushdown
while(1){
if(tree[tree[u].son[0]].siz>=rk){
u=tree[u].son[0];
}
else if(tree[tree[u].son[0]].siz+tree[u].cnt>=rk) return u;
else{
rk-=tree[tree[u].son[0]].siz+tree[u].cnt;
u=tree[u].son[1];
}
pushdown(u);
}
}
inline void reverse(int l,int r){
l=query(l-1);r=query(r+1);//找到序列中第 l-1 个数和第 r+1 个数的位置
splay(l,0);splay(r,l);//如上图
int tmp=tree[r].son[0];//找到上图中三角形那个子树，打上翻转 tag
tree[tmp].tag^=1;
}
对于这道模板题，再进行了全部翻转之后，最后中序遍历一次输出结果即可，这里不再做细节的阐述。
至此，Luogu3391 就被解决了，我们接着给出 Splay 中其他操作的代码。
与 treap 的递归写法不同，Splay 我采用了循环写法，思想类似，但个人写 Splay 的时候发觉循环写着比较容易，就写了循环（treap 在 insert 中需要递归回来进行旋转，故递归写法更合适些，而查询等与 BST 类似的操作同样可以用循环写法）。
查询排名为 $x$ 的数就是上边代码中的 query，不再重复。
插入
inline void insert(int x){
int u=root,fa=0;
while(tree[u].val!=x&&u){
fa=u;
u=tree[u].son[x>tree[u].val];//判断往左儿子走还是往右儿子走
}
if(u) tree[u].cnt++;
else{
u=++cnt;
if(fa) tree[fa].son[x>tree[fa].val]=u;
tree[u].fa=fa;tree[u].val=x;
tree[u].cnt=tree[u].siz=1;
}
splay(u,0);//插入完了 splay 一下
}
查询 $x$ 数的排名
这个操作比较有意思，实现方法就是把 $x$ 数旋转到根上来，然后直接回答左儿子的大小（当然还要判断一下根节点，因为询问的数不一定存在）。
实际上，find 函数在查找前驱/后继时也有用，看下去即可明白。
inline void find(int x){
int u=root;
while(x!=tree[u].val&&tree[u].son[x>tree[u].val]){
u=tree[u].son[x>tree[u].val];
}
splay(u,0);
}
………………
find(x);
int tmp=tree[tree[root].son[0]].siz;//见下面小 tip
if(tree[root].val<x) tmp+=tree[root].cnt;
printf("%d\n",tmp);
小 Tip
Splay 还有一个小 tip，因为它天旋地转的，所以建议在操作之前先 insert(-inf);insert(inf); 防止旋转时跑丢（比如翻转区间时，如果翻转的是整个区间，没有这俩就会出问题）。同时，由于这两个数，代码细节上会有些许改变，比如查询排名时不需要再 $+1$，原因显然。
求 $x$ 的前驱/后继
对于这个操作，我们先把 $x$ 找到并旋转到根节点，那么前驱显然就是左子树中最右的，后继反之。
inline int frne(int x,int opt){//opt=0 前驱,opt=1 后继
find(x);//看前面
int u=root;
if((!opt&&tree[u].val<x)||(opt&&tree[u].val>x)) return u;
u=tree[u].son[opt];//向左子树走
while(tree[u].son[opt^1]) u=tree[u].son[opt^1];//然后一直往右
return u;
}
删除
学习了前边两个，才可以学习删除操作。Splay 中的删除操作比较特殊，先找到 $x$ 的前驱和后继（显然 $x$ 就是被夹在中间的糕点），然后像区间翻转时的操作那样，把前驱翻转到根，后继反转到根的右儿子，然后后继的左儿子自然就是要删除的那个数了。
inline void del(int x){
int l=frne(x,0);//看前面
int r=frne(x,1);
splay(l,0);splay(r,l);
int tmp=tree[r].son[0];
if(tree[tmp].cnt>1){//同样要分类
tree[tmp].cnt--;
splay(tmp,0);
}
else tree[r].son[0]=0;
}
这样 Splay 就学完啦！与 treap 不同，Splay 通过 splay 操作可以玩出很多花样（看独特的删除和找前驱/后继就知道啦），虽然似乎跑的比 treap 慢一点，但是却是一个延展性很大的算法。
一道练手题
Luogu2042 [NOI2005] 维护数列 平衡树维护数列，考察 Splay，思维难度不大但代码挺长的，适合练手以加深理解。
最后在文末给出本文中 Luogu3369 和 Luogu3391 两道模板题的 AC 代码。
完整代码（无注释）
Luogu3369 【模板】普通平衡树 – 使用 Treap 实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=2147483647;
struct node{
int ls,rs,w,siz,val,rnd;
}tr[N];
int n,cnt,root,tot;
inline void update(int x){
tr[x].siz=tr[tr[x].ls].siz+tr[tr[x].rs].siz+tr[x].w;
}
inline void rturn(int &x){
int t=tr[x].ls;tr[x].ls=tr[t].rs;tr[t].rs=x;
tr[t].siz=tr[x].siz;update(x);x=t;
}
inline void lturn(int &x){
int t=tr[x].rs;tr[x].rs=tr[t].ls;tr[t].ls=x;
tr[t].siz=tr[x].siz;update(x);x=t;
}
inline void insert(int &x,int v){
if(x==0){
cnt++;x=cnt;
tr[x].siz=tr[x].w=1;
tr[x].val=v;tr[x].rnd=rand();
return;
}
tr[x].siz++;
if(tr[x].val==v){
tr[x].w++;
return;
}
if(v>tr[x].val){
insert(tr[x].rs,v);
if(tr[tr[x].rs].rnd<tr[x].rnd) lturn(x);
}
else{
insert(tr[x].ls,v);
if(tr[tr[x].ls].rnd<tr[x].rnd) rturn(x);
}
}
inline void del(int &x,int v){
if(x==0) return;
if(tr[x].val==v){
if(tr[x].w>1){
tr[x].w--;tr[x].siz--;return;
}
if(tr[x].ls==0||tr[x].rs==0) x=tr[x].ls+tr[x].rs;
else if(tr[tr[x].ls].rnd<tr[tr[x].rs].rnd){
rturn(x);
del(x,v);
}
else{
lturn(x);
del(x,v);
}
}
else if(v>tr[x].val){
tr[x].siz--;del(tr[x].rs,v);
}
else{
tr[x].siz--;del(tr[x].ls,v);
}
}
inline int queryrk(int x,int v){
if(x==0) return 0;
if(tr[x].val==v) return tr[tr[x].ls].siz;
if(v>tr[x].val) return tr[tr[x].ls].siz+tr[x].w+queryrk(tr[x].rs,v);
return queryrk(tr[x].ls,v);
}
inline int querynum(int x,int rk){
if(x==0) return 0;
if(rk<=tr[tr[x].ls].siz) return querynum(tr[x].ls,rk);
if(rk<=tr[tr[x].ls].siz+tr[x].w) return tr[x].val;
return querynum(tr[x].rs,rk-tr[tr[x].ls].siz-tr[x].w);
}
inline int queryfr(int x,int v,int ans){
if(tr[x].val>=v){
if(!tr[x].ls) return ans;
return queryfr(tr[x].ls,v,ans);
}
else{
if(!tr[x].rs) return tr[x].val;
return queryfr(tr[x].rs,v,tr[x].val);
}
}
inline int queryne(int x,int v,int ans){
if(tr[x].val<=v){
if(!tr[x].rs) return ans;
return queryne(tr[x].rs,v,ans);
}
else{
if(!tr[x].ls) return tr[x].val;
return queryne(tr[x].ls,v,tr[x].val);
}
}
int main(){
scanf("%d",&n);
for(int i=1,opt,x;i<=n;i++){
scanf("%d%d",&opt,&x);
if(opt==1){
if(tot==0){
cnt++;
root=cnt;
tr[cnt].siz=tr[cnt].w=1;
tr[cnt].val=x;tr[cnt].rnd=rand();
}
else insert(root,x);
tot++;
}
else if(opt==2){
del(root,x);
tot--;
}
else if(opt==3) printf("%d\n",queryrk(root,x)+1);
else if(opt==4) printf("%d\n",querynum(root,x));
else if(opt==5) printf("%d\n",queryfr(root,x,-inf));
else printf("%d\n",queryne(root,x,inf));
}
return 0;
}
Luogu3369 【模板】普通平衡树 – 使用 Splay 实现
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct Splay_Tree{
int son[2],fa,cnt,val,siz;
}tree[N];
int n,root,cnt;
const int inf=2147483647;
inline void update(int u){
tree[u].siz=tree[tree[u].son[0]].siz+tree[tree[u].son[1]].siz+tree[u].cnt;
}
inline bool check(int u){
return tree[tree[u].fa].son[1]==u;
}
inline void rotate(int u){
int fa=tree[u].fa;
int ffa=tree[fa].fa;
int k=check(u);
tree[ffa].son[check(fa)]=u;tree[u].fa=ffa;
tree[fa].son[k]=tree[u].son[k^1];tree[tree[u].son[k^1]].fa=fa;
tree[u].son[k^1]=fa;tree[fa].fa=u;
update(fa);update(u);
}
inline void splay(int u,int goal){
while(tree[u].fa!=goal){
int fa=tree[u].fa;
int ffa=tree[fa].fa;
if(ffa!=goal){
if(check(u)==check(fa)) rotate(fa);
else rotate(u);
}
rotate(u);
}
if(!goal) root=u;
}
inline void insert(int x){
int u=root,fa=0;
while(tree[u].val!=x&&u){
fa=u;
u=tree[u].son[x>tree[u].val];
}
if(u) tree[u].cnt++;
else{
u=++cnt;
if(fa) tree[fa].son[x>tree[fa].val]=u;
tree[u].fa=fa;tree[u].val=x;
tree[u].cnt=tree[u].siz=1;
}
splay(u,0);
}
inline void find(int x){
int u=root;
while(x!=tree[u].val&&tree[u].son[x>tree[u].val]){
u=tree[u].son[x>tree[u].val];
}
splay(u,0);
}
inline int frne(int x,int opt){
find(x);
int u=root;
if((!opt&&tree[u].val<x)||(opt&&tree[u].val>x)) return u;
u=tree[u].son[opt];
while(tree[u].son[opt^1]) u=tree[u].son[opt^1];
return u;
}
inline void del(int x){
int l=frne(x,0);
int r=frne(x,1);
splay(l,0);splay(r,l);
int tmp=tree[r].son[0];
if(tree[tmp].cnt>1){
tree[tmp].cnt--;
splay(tmp,0);
}
else tree[r].son[0]=0;
}
inline int query(int rk){
int u=root;
while(1){
if(tree[tree[u].son[0]].siz>=rk){
u=tree[u].son[0];
}
else if(tree[tree[u].son[0]].siz+tree[u].cnt>=rk) return u;
else{
rk-=tree[tree[u].son[0]].siz+tree[u].cnt;
u=tree[u].son[1];
}
}
}
int main(){
insert(-inf);insert(inf);
scanf("%d",&n);
for(int i=1,opt,x;i<=n;i++){
scanf("%d%d",&opt,&x);
if(opt==1) insert(x);
else if(opt==2) del(x);
else if(opt==3){
find(x);
int tmp=tree[tree[root].son[0]].siz;
if(tree[root].val<x) tmp+=tree[root].cnt;
printf("%d\n",tmp);
}
else if(opt==4) printf("%d\n",tree[query(x+1)].val);
else if(opt==5) printf("%d\n",tree[frne(x,0)].val);
else printf("%d\n",tree[frne(x,1)].val);
}
return 0;
}
Luogu3391 【模板】文艺平衡树 – 使用 Splay 实现
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct Splay_Tree{
int son[2],fa,cnt,val,siz,tag;
}tree[N];
int n,root,cnt,m,a[N];
const int inf=2147483647;
inline void update(int u){
tree[u].siz=tree[tree[u].son[0]].siz+tree[tree[u].son[1]].siz+tree[u].cnt;
}
inline void pushdown(int x){
if(tree[x].tag){
tree[tree[x].son[0]].tag^=1;
tree[tree[x].son[1]].tag^=1;
swap(tree[x].son[0],tree[x].son[1]);
tree[x].tag=0;
}
}
inline int build(int l,int r,int fa){
if(l>r) return 0;
int v=++cnt;
tree[v].fa=fa;
tree[v].cnt=1;
int mid=(l+r)>>1;
tree[v].val=a[mid];
tree[v].son[0]=build(l,mid-1,v);
tree[v].son[1]=build(mid+1,r,v);
update(v);
return v;
}
inline bool check(int u){
return tree[tree[u].fa].son[1]==u;
}
inline void rotate(int u){
int fa=tree[u].fa;
int ffa=tree[fa].fa;
pushdown(u);pushdown(fa);
int k=check(u);
tree[ffa].son[check(fa)]=u;tree[u].fa=ffa;
tree[fa].son[k]=tree[u].son[k^1];tree[tree[u].son[k^1]].fa=fa;
tree[u].son[k^1]=fa;tree[fa].fa=u;
update(fa);update(u);
}
inline void splay(int u,int goal){
while(tree[u].fa!=goal){
int fa=tree[u].fa;
int ffa=tree[fa].fa;
pushdown(u);pushdown(fa);
if(ffa!=goal){
if(check(u)==check(fa)) rotate(fa);
else rotate(u);
}
rotate(u);
}
if(!goal) root=u;
}
inline int query(int rk){
int u=root;
pushdown(u);
while(1){
if(tree[tree[u].son[0]].siz>=rk){
u=tree[u].son[0];
}
else if(tree[tree[u].son[0]].siz+tree[u].cnt>=rk) return u;
else{
rk-=tree[tree[u].son[0]].siz+tree[u].cnt;
u=tree[u].son[1];
}
pushdown(u);
}
}
inline void getans(int x){
pushdown(x);
if(tree[x].son[0]) getans(tree[x].son[0]);
if(tree[x].val!=inf&&tree[x].val!=-inf) printf("%d ",tree[x].val);
if(tree[x].son[1]) getans(tree[x].son[1]);
}
inline void reverse(int l,int r){
l=query(l-1);r=query(r+1);
splay(l,0);splay(r,l);
int tmp=tree[r].son[0];
tree[tmp].tag^=1;
}
int main(){
scanf("%d%d",&n,&m);
a[1]=-inf,a[n+2]=inf;
for(int i=1;i<=n;i++){
a[i+1]=i;
}
root=build(1,n+2,0);
for(int i=1,l,r;i<=m;i++){
scanf("%d%d",&l,&r);
reverse(l+1,r+1);
}
getans(root);
return 0;
}