题目描述：https://www.luogu.org/problemnew/show/P3391
解析：在这里主要讲一下对splay上点的权值的看法。首先，我们发现一颗splay的中序遍历始终是不变的，所以想到用splay的中序遍历来表示原数组的位置。那么怎么实现呢？我们只需要刚开始建树的时候以位置为权值来建树。换一种说法，以位置建树只是为了让splay的中序遍历有序。所以事实上，这颗splay任然是以原数组的数为权值的，只不过是刚开始建树的时候换了一个建树方式。那么有同学可能会问，swap过后不就不满足splay左小右大的性质了吗？肯定不满足啊。有同学可能会问另外一个问题，怎么保证r+1一定能旋转到l-1的右儿子去呢，不是已经不满足splay的性质了吗？注意，splay的旋转操作是跟点的权值没有关系的，它只是跟splay怎么建的树有关系。
附上代码(origin为原数组)：
#include<cstdio> #include<algorithm> using namespace std; const int MAXN=100005; int n,m; int root; struct Node{ int size,son[2],val,fa,tag; }node[MAXN]; int ndnum=0; int origin[MAXN]; int check(int x){ return x==node[node[x].fa].son[1]; } void update(int x){ node[x].size=node[node[x].son[0]].size+node[node[x].son[1]].size+1; } void rotate(int x){ int y=node[x].fa,z=node[y].fa,d=check(x),xx=node[x].son[d^1]; node[y].son[d]=xx;node[xx].fa=y; node[z].son[check(y)]=x;node[x].fa=z; node[x].son[d^1]=y;node[y].fa=x; update(y);update(x); } void splay(int x,int to=0){ while(node[x].fa!=to){ int y=node[x].fa,z=node[y].fa; if(z!=to){ if(check(x)==check(y)) rotate(y); else rotate(x); } rotate(x); } if(!to) root=x; } void insert(int x){ int cur=root,f=0; while(cur&&node[cur].val!=x){ f=cur; cur=node[cur].son[x>node[cur].val]; } cur=++ndnum; if(f) node[f].son[x>node[f].val]=cur; node[cur].size=1;node[cur].tag=0; node[cur].son[0]=node[cur].son[1]=0; node[cur].val=x;node[cur].fa=f; splay(cur); } void pushdown(int cur){ if(node[cur].tag){ node[node[cur].son[0]].tag^=1; node[node[cur].son[1]].tag^=1; node[cur].tag=0; swap(node[cur].son[0],node[cur].son[1]); } } int kth(int k){ int cur=root; while(1){ pushdown(cur); if(k<=node[node[cur].son[0]].size) cur=node[cur].son[0]; else{ k-=node[node[cur].son[0]].size+1; if(!k) return cur; cur=node[cur].son[1]; } } } void reserve(int l,int r){ l=kth(l-1);r=kth(r+1); splay(l);splay(r,l); node[node[node[root].son[1]].son[0]].tag^=1; } void write(int cur){ pushdown(cur); if(node[cur].son[0]) write(node[cur].son[0]); if(node[cur].val>1&&node[cur].val<n+2) printf("%d ",origin[node[cur].val-1]); if(node[cur].son[1]) write(node[cur].son[1]); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&origin[i]); for(int i=1;i<=n+2;i++) insert(i); for(int i=1;i<=m;i++){ int l,r; scanf("%d%d",&l,&r); reserve(l+1,r+1); } write(root); return 0; }