题目背景
这是一道经典的Splay模板题——文艺平衡树。
题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
输入输出格式
输入格式：
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2,⋯n−1,n) m表示翻转操作次数
接下来m行每行两个数 [l,r]数据保证 1≤l≤r≤n
输出格式：
输出一行n个数字，表示原始序列经过m次变换后的结果
输入输出样例
5 3
1 3
1 3
1 4
4 3 2 1 5
说明
n,m≤100000 n, m
Splay的简介：
1 简介：
伸展树，或者叫自适应查找树，是一种用于保存有序集合的简单高效的数据结构。伸展树实质上是一个二叉查找树。允许查找，插入，删除，删除最小，删除最大，分割，合并等许多操作，这些操作的时间复杂度为O(logN)。由于伸展树可以适应需求序列，因此他们的性能在实际应用中更优秀。
伸展树支持所有的二叉树操作。伸展树不保证最坏情况下的时间复杂度为O(logN)。伸展树的时间复杂度边界是均摊的。尽管一个单独的操作可能很耗时，但对于一个任意的操作序列，时间复杂度可以保证为O(logN)。
2 自调整和均摊分析：
平衡查找树的一些限制：
1、平衡查找树每个节点都需要保存额外的信息。
2、难于实现，因此插入和删除操作复杂度高，且是潜在的错误点。
3、对于简单的输入，性能并没有什么提高。
平衡查找树可以考虑提高性能的地方：
1、平衡查找树在最差、平均和最坏情况下的时间复杂度在本质上是相同的。
2、对一个节点的访问，如果第二次访问的时间小于第一次访问，将是非常好的事情。
3、90-10法则。在实际情况中，90%的访问发生在10%的数据上。
4、处理好那90%的情况就很好了。
3 均摊时间边界：
在一颗二叉树中访问一个节点的时间复杂度是这个节点的深度。因此，我们可以重构树的结构，使得被经常访问的节点朝树根的方向移动。尽管这会引入额外的操作，但是经常被访问的节点被移动到了靠近根的位置，因此，对于这部分节点，我们可以很快的访问。根据上面的90-10法则，这样做可以提高性能。
为了达到上面的目的，我们需要使用一种策略──旋转到根(rotate-to-root)。
上面所说的，我来举个例子解释一下：假设有这样一道题，有100000次操作，每次输入a,b，若a为0表示将b放入数列中，若a为1表示输出第b大的数。这道题看似简单，不就直接二叉搜索树嘛！但是如果数b是单调递增出现的，则树会成链，那么还是O(n^2)的复杂度。此时我们边用到了Splay，由于splay是不断翻转的，所以就算某一时刻他成了一条链，也会马上旋转而变成另外的形态（深度减低），通过这样不断地变换可以防止长期停留在链的状态，以保证每次操作平均复杂度O（log n）。
Splay的实现：
有话要说：
关于Splay，我觉得自己已经完全掌握了，让我口头说还可以，但是要写篇详解实在是时间又少而且没精力（而且大神们的博客已经写的非常到位了，自己写的肯定不及他们），所以这里我提供本人自学Splay时所看的一些比较有用的博客：1、基础(非指针) 2、基础（指针） 3、应用
认真看上述博客并思考，便会发现Splay其实很简单。
Splay应用：
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
关于这道题：
只要我们弄懂Splay，其实本题很简单：首先按照中序遍历建树，然后对于每次修改区间l,r，首先得提出这段区间，方法是将l的前趋l-1旋转到根节点，将r的后趋r+1旋转到根节点的右儿子，我们可以自己画图试试，容易发现经过这个操作后，根节点的右儿子的左子树（具体应该说是这个左子树的中序遍历）就是区间l-r。关键的翻转时，因为树是中序遍历（左根右），所以我们只要将l-r（前面所说的根节点的右儿子的左子树）这个区间子树左右儿子的节点交换位置（这样再中序遍历相当于右根左，即做到了翻转操作）。关键是翻转的优化，我们用到懒惰标记lazy[x]（表示x是否翻转），每次翻转时只要某个节点有标记且在翻转的区间内，则将标记下放给它的两个儿子节点且将自身标记清0，这样便避免了多余的重复翻转。（不懂画图看博客）
1、裸代码：
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define debug printf("%d %s\n",__LINE__,__FUNCTION__)
using namespace std;
const int N=;
il int gi()
{
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=;
while(x>=''&&x<='')a=a*+x-,x=getchar();
return f?-a:a;
}
int n,m,tot,root,siz[N],fa[N],flag[N],key[N],ch[N][],cnt[N],ans[N];
il void update(int rt)
{
int l=ch[rt][],r=ch[rt][];
siz[rt]=siz[l]+siz[r]+;
}
il void pushdown(int now)
{
if(flag[now]){
flag[ch[now][]]^=;
flag[ch[now][]]^=;
swap(ch[now][],ch[now][]);
flag[now]=;
}
}
il int getson(int x){return ch[fa[x]][]==x;}
il void rotate(int x)
{
int y=fa[x],z=fa[y],b=getson(x),c=getson(y),a=ch[x][!b];
if(z)ch[z][c]=x;else root=x;fa[x]=z;
if(a)fa[a]=y;ch[y][b]=a;
ch[x][!b]=y;fa[y]=x;
update(y);update(x);
}
il void splay(int x,int i)
{
while(fa[x]!=i){
int y=fa[x],z=fa[y];
if(z==i)rotate(x);
else {
if(getson(x)==getson(y)){rotate(y);rotate(x);}
else {rotate(x);rotate(x);}
}
}
}
il int find(int x)
{
int now=root;
while(){
pushdown(now);
if(ch[now][]&&x<=siz[ch[now][]])now=ch[now][];
else {
int tmp=(ch[now][]?siz[ch[now][]]:)+;
if(x<=tmp)return now;
x-=tmp;
now=ch[now][];
}
}
}
il int build(int l,int r,int rt)
{
int now=l+r>>;
fa[now]=rt;
key[now]=ans[now];
if(l<now)ch[now][]=build(l,now-,now);
if(r>now)ch[now][]=build(now+,r,now);
update(now);
return now;
}
il void print(int now)
{
pushdown(now);
if(ch[now][])print(ch[now][]);
ans[++tot]=key[now];
if(ch[now][])print(ch[now][]);
}
int main()
{
n=gi(),m=gi();int x,y;
for(int i=;i<=n+;i++)ans[i]=i-;
root=build(,n+,);
for(int i=;i<=m;i++){
x=gi(),y=gi();
x=find(x),y=find(y+);
splay(x,);splay(y,x);
flag[ch[ch[root][]][]]^=;
}
print(root);
for(int i=;i<=n;i++)printf("%d ",ans[i+]);
return ;
}
2、方便理解，带注释代码：
/*Splay只记模板是很困难的，而且真正运用时易生疏出错，所以必须理解，在看代码前先弄懂
Splay的原理，这篇代码是带注释的Splay模板，题目来自洛谷P3391 ———————————by 520*/
#include<bits/stdc++.h>
#define il inline
#define debug printf("%d %s\n",__LINE__,__FUNCTION__)
using namespace std;
const int N=;
il int gi()
{
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=;
while(x>=''&&x<='')a=a*+x-,x=getchar();
return f?-a:a;
} int n,m,tot,root,siz[N],fa[N],lazy[N],key[N],tree[N][],ans[N];
/*root为根节点,siz存储子树节点数，fa存储父节点，lazy是懒惰标记用来标记区间翻转操作，key数组存储原数列，tree为
splay树，ans存储答案*/ il void pushup(int rt) //作用类似与线段树
{
int l=tree[rt][],r=tree[rt][]; //pushup作用是将子树的节点个数更新给根节点
siz[rt]=siz[l]+siz[r]+;
} il void pushdown(int now)
{
if(lazy[now]){
lazy[tree[now][]]^=;
lazy[tree[now][]]^=; /*pushdown作用是下放懒惰标记，若某一节点所在子树（即某一区间）被翻转
，则将懒惰标记下放给两个儿子节点，交换左右儿子位置（中序遍历，交换左右儿子后相当于翻转）并对所在子树根节
点的标记清0,*/
swap(tree[now][],tree[now][]);
lazy[now]=;
}
} il int getson(int x){return tree[fa[x]][]==x;} //getson判断x是其父亲的右儿子还是左儿子 il void rotate(int x) //旋转操作，直接写在一个函数里，可以称为上旋
{
int y=fa[x],z=fa[y],b=getson(x),c=getson(y),a=tree[x][!b]; /*y是x的父节点，z是y的父节点，getson解释过了。
特别解释一下a，a为旋转时需要移动的子树，若x为左儿子则右旋时要将x的右子树移动，同理若x为右儿子则左旋时要
将x的左子树移动，所以这里a=tree[x][!b]*/
if(z)tree[z][c]=x;else root=x;fa[x]=z; /*若z不为根节点，则用x替代y的位置;若z为根节点，则将x变为根节点。*/
if(a)fa[a]=y;tree[y][b]=a; /*若存在要移动的子树a，则把a和y相连，取代原来x的位置*/
tree[x][!b]=y;fa[y]=x; /*!b的原因：若x为左儿子则旋转后y为x的右儿子，若x为右儿子则旋转后y为x的左儿子。记得将y
指向x*/
pushup(y);pushup(x); /*旋转后，对被移动了的y和x更新它们各自的子树节点数*/
} il void splay(int x,int i)
{
while(fa[x]!=i){ //只要x没有旋转到需要的点下面，则一直旋，注意根节点的父亲为虚点0
int y=fa[x],z=fa[y];
if(z==i)rotate(x); //若x的爷爷是i，则只需旋一次
else {
if(getson(x)==getson(y)){rotate(y);rotate(x);} /*若x和y为相同偏向，则进行Zig-Zig或Zag-Zag操作*/
else {rotate(x);rotate(x);} /*否则进行Zig-Zag或Zag-Zig操作*/
/*注意rotate函数中已经包含了这四种操作情况了*/
}
}
} il int find(int x) //查找x的位置
{
int now=root; //从根节点往下
while(){
pushdown(now); //本次操作要将前面的标记进行翻转
if(tree[now][]&&x<=siz[tree[now][]])now=tree[now][]; //若存在左子树且x小于等于左子树的节点数，则x在左子树上
else {
int tmp=(tree[now][]?siz[tree[now][]]:)+; //往右子树找，+1代表加上这个子树的根节点
if(x==tmp)return now; //若找到了x，返回它的位置
x-=tmp; //否则x减去根节点右子树以外的节点数，这个画图能理解，因为siz值并不是直接的x的值
now=tree[now][]; //将原来根节点的右儿子赋为新的根节点，继续递归查找x位置
}
}
} il int build(int l,int r,int rt) //建树过程和线段树类似
{
int now=l+r>>;
fa[now]=rt;
key[now]=ans[now]; //key存原数组1到n，准确说是0到n+1,原因是主函数里的预处理
if(l<now)tree[now][]=build(l,now-,now);
if(r>now)tree[now][]=build(now+,r,now);
pushup(now); //记得pushup
return now;
} il void print(int now) //输出时中序遍历，按左根右输出
{
pushdown(now); //记得要翻转
if(tree[now][])print(tree[now][]); //因为中序遍历左根右，所以递归根节点左子树到第一个数的位置
ans[++tot]=key[now]; //回溯时存储答案,注意我们翻转操作的是原数组下标
if(tree[now][])print(tree[now][]); //同理递归根节点的右子树
} int main()
{
n=gi(),m=gi();int x,y;
for(int i=;i<=n+;i++)ans[i]=i-; /*因为取出操作区间时旋转的是x的前驱和y的后驱，所以预处理时第i个点
存的是i的前驱*/
root=build(,n+,);
while(m--)
{
x=gi(),y=gi();
x=find(x),y=find(y+); /*查找x的前驱所在的位置，和y后驱所在的位置，因为预处理时ans存的是前趋，
所以直接查找x，而y的后驱变成了y+2*/
splay(x,);splay(y,x); /*将x前驱上旋至根节点，y的后驱上旋成根节点右儿子的左子树*/
lazy[tree[tree[root][]][]]^=;//经过旋转后，此时根节点的右儿子的左子树就是需要翻转的区间，所以lazy标记
}
print(root);
for(int i=;i<=n;i++)printf("%d ",ans[i+]); //输出时将前驱还原为原数
return ;
}