您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是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次变换后的结果
这题目调了我好久，最后发现是全局变量的锅qwq。
最近刚学Splay，总算搞明白了Splay维护序列的原理。就来发题解记录一下。
首先我们的这一颗Splay的中序遍历即为我们要求的结果。这里的Splay并不是传统意义上的平衡二叉树（即某个节点的左儿子的权值小于该节点的权值，右儿子节点的权值大于该节点的权值）节点权值在这里除了最后输出是没有意义的。我们其实是用一个数在Splay中的排名来代表原序列上这个排名的所在位置的（注意是所在位置，并不代表某一特定值）。
然后我们考虑如何找出区间$[l,r]$，我们首先将排名为$l-1$的节点一路旋转到根，然后将排名为$r+1$的节点旋转为根节点的右儿子（此时它一定在根节点右子树中，因为排名比根节点的排名$l-1$更大）。然后此时根节点的右儿子的左子树内就是我们要求的区间$[l,r]$的位置了（因为这里面的数都是排名大于$l-1$且小于$r+1$的，可以考虑二叉查找树的性质）。然后将左右子树互换就好了(也是二叉查找树的性质)，注意交换后节点的权值变了，但是所代表的位置是不变的。
最后用两个哨兵$(0$与$n+1)$什么的来防止找不到$l-1$与$r+1$，建树无所谓，像线段树那样建没关系。然后在加上延迟标记，等要访问这个节点的时候再交换左右子节点。
附上代码：
#include<bits/stdc++.h> using namespace std; const int inf=1<<30; const int N=100005; int w[N],f[N],size[N],value[N],tag[N],tr[N][2]; int n,m,sz,root; int read(){ int x=0; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return x; } int get(int x){return tr[f[x]][1]==x;} void updata(int x){if(x) size[x]=size[tr[x][0]]+size[tr[x][1]]+1;} void pushdown(int x){ if(x && tag[x]){ tag[tr[x][0]]^=1; tag[tr[x][1]]^=1; swap(tr[x][0],tr[x][1]); tag[x]=0; } } void rotate(int x){//正常旋转函数 int fa=f[x],gfa=f[fa]; int now=get(x); tr[fa][now]=tr[x][now^1],f[tr[fa][now]]=fa; tr[x][now^1]=fa,f[fa]=x; f[x]=gfa; if(gfa) tr[gfa][tr[gfa][1]==fa]=x; updata(x),updata(fa); } void Splay(int x,int goal){//Splay加了目标 for(int fa;(fa=f[x])!=goal;rotate(x)){ if(f[fa]!=goal){ rotate(get(fa)==get(x) ? fa : x); } } if(!goal) root=x; } int build(int l,int r,int fa){//建树 if(l>r) return 0; int mid=(l+r)>>1; int now=++sz; f[now]=fa; value[now]=w[mid]; tr[now][0]=build(l,mid-1,now); tr[now][1]=build(mid+1,r,now); updata(now); return now; } int find(int x){//查找排名函数 int now=root; while(1){ pushdown(now); if(x<=size[tr[now][0]]) now=tr[now][0]; else{ x-=size[tr[now][0]]+1; if(!x) return now; now=tr[now][1]; } } } void reserve1(int l,int r){ l=find(l),r=find(r);//先找排名 Splay(l,0),Splay(r,l);//把l转移到根节点，r转移到l的右儿子 tag[tr[tr[root][1]][0]]^=1;//打上标记 } void dfs(int x){//最后中序遍历输出答案 pushdown(x); if(tr[x][0]) dfs(tr[x][0]); if(value[x]!=inf && value[x]!=-inf){ printf("%d ",value[x]); } if(tr[x][1]) dfs(tr[x][1]); } int main(){ n=read(),m=read(); w[0]=-inf,w[n+1]=inf; for(int i=1;i<=n;++i) w[i]=i; root=build(0,n+1,0);//建树 for(int i=1,l,r;i<=m;++i){ l=read(),r=read(); reserve1(l,r+2);//因为用了哨兵所以并不是我说的$l-1$与$r+1$ } dfs(root); return 0; }
原文：https://www.cnblogs.com/Asika3912333/p/11767945.html