这道题在好多测评网站都可以提交。
这次用平衡树维护的不是每个数的值，而是顺序。
至于区间操作，每次把左边界左边的那个点旋转到根，把右边界右边的那个点旋转到根的右儿子。
然后你就会惊讶（并不）地发现：这个区间都被转到蓝色区域去了！（毕竟是l-1<rank<r+1的部分）
这样就可以在这个区间的根节点，也就是图中的点x，上进行标记。
至于pushdown的细节，也没什么好说的。
但要注意l-1和r+1可能会是不存在的点，因此在建splay时要在左右边界额外各放一个。
（并不对劲的一点看法：这题应该能用别的平衡树做，就是每次把该转到根的转到根再转回去吧，听说常数会更小。但有什么用呢？反正心中有党常数极小）
这道题为什么要用splay维护区间反转呢？想必是和某个L开头T结尾的玩意儿有关的。
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<iomanip> #include<cstdlib> #define maxn 100010 #define mod 1000000 using namespace std; int read(){ int x=0,f=1; char ch=getchar(); while(isdigit(ch)==0 && ch!='-')ch=getchar(); if(ch=='-')f=-1; while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f; } typedef struct node{ int son[2],fa;//0左，1右 int key,re,siz; }Tree; typedef struct array{ int a[maxn]; }A; int n,m; A b; struct Splay { int cnt,root; Tree x[maxn]; inline void pushdown(int u){ if(x[u].re){ x[u].re=0; swap(x[u].son[0],x[u].son[1]); x[x[u].son[0]].re^=1; x[x[u].son[1]].re^=1; } } inline void pushup(int u){ x[u].siz=x[x[u].son[0]].siz+x[x[u].son[1]].siz+1; } inline void rot(int u){ int fu=x[u].fa,ffu=x[fu].fa,l=(x[fu].son[1]==u),r=l^1; int l2=(fu==x[ffu].son[1]); x[ffu].son[l2]=u; x[u].fa=ffu; x[fu].fa=u; x[fu].son[l]=x[u].son[r]; x[x[u].son[r]].fa=fu; x[u].son[r]=fu; pushup(fu),pushup(u); } inline void splay(int u,int k){ while(x[u].fa!=k){ int fu=x[u].fa,ffu=x[fu].fa; if(ffu!=k){ if((x[ffu].son[0]==x[u].fa)^(x[fu].son[0]==u)) rot(u); else rot(fu); } rot(u); } if(k==0)root=u; } inline int res(int k,int f){ x[++cnt].key=k, x[cnt].fa=f, x[cnt].re=0;x[cnt].siz=1; return cnt; } /*inline void ins(int k){ int lst=0,u=root; while(u){ pushdown(u); if(x[x[u].son[0]].siz+1==k)break; x[u].siz++;int rk=x[x[u].son[0]].siz+1; lst=u,u=x[u].son[rk<k],k=k>rk?k-rk:k; } if(u==0){ u=res(k,lst,0,0); if(lst)x[lst].son[x[lst].key<k]=u; } splay(u,0); }*/ inline int rnk(int k){//the number of the kth number int u=root; if(u==0)return 0; while(u){ pushdown(u); int rk=x[x[u].son[0]].siz+1; if(rk==k)break; u=x[u].son[k>rk]; k=k>rk?k-rk:k; } //splay(u,0); return u; } /*inline void del(int k){ int lk=rnk(k-1), rk=rnk(k+1); splay(lk,0),splay(rk,lk); x[rk].son[0]=0; }*/ inline void rev(int l,int r){ int lk=rnk(l-1),rk=rnk(r+1); splay(lk,0),splay(rk,lk); x[x[rk].son[0]].re^=1; pushdown(x[rk].son[0]); } inline void prt(int u){ pushdown(u); if(x[u].son[0])prt(x[u].son[0]); if(x[u].key!=-1)printf("%d ",x[u].key); if(x[u].son[1])prt(x[u].son[1]); } void start(){ cnt=root=0; } }t; inline int bld(int l,int r,int lst){ if(l>r)return 0; if(l==r){ return t.res(b.a[l],lst); } else{ int m=(l+r)>>1; int u=t.res(b.a[m],lst); int ls=bld(l,m-1,u); int rs=bld(m+1,r,u); t.x[u].son[0]=ls,t.x[u].son[1]=rs; t.pushup(u); return u; } } int main() { //cout<<" I hate Splay"<<endl; n=read(),m=read(); b.a[0]=b.a[n+1]=-1; for(int i=1;i<=n;i++) b.a[i]=i; t.root=1; bld(0,n+1,0); while(m--){ int x=read(),y=read(); t.rev(x+1,y+1); } t.prt(t.root); return 0; }
其实这是AC的