splay模板。。。
此题考的是splay支持区间反转的性质
为之后学LCT做铺垫 （语文阅读做多了。。。）
写的好丑：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,tot,rt; int num[100005]; struct Tree{ int val; int siz; int mark; int fa; int son[2]; }tr[100005]; void update(int x){ tr[x].siz=tr[tr[x].son[0]].siz+tr[tr[x].son[1]].siz+1; } void markdown(int x){ if(tr[x].mark){ tr[tr[x].son[0]].mark^=1; tr[tr[x].son[1]].mark^=1; tr[x].mark=0; swap(tr[x].son[0],tr[x].son[1]); } } void rotate(int x){ int y=tr[x].fa,z=tr[y].fa; int typ=(x==tr[y].son[1]); tr[y].son[typ]=tr[x].son[typ^1],tr[tr[x].son[typ^1]].fa=y; tr[x].son[typ^1]=y,tr[y].fa=x; tr[x].fa=z; if(z){ if(tr[z].son[0]==y)tr[z].son[0]=x; else tr[z].son[1]=x; } update(y);update(x); } void splay(int x,int goal){
for(int y;(y=tr[x].fa)!=goal;rotate(x)){
if(tr[y].fa!=goal){
rotate((x==tr[y].son[0])==(y==tr[tr[y].fa].son[0])?y:x);
}
}
if(!goal){
rt=x;
}
} void insert(int x,int v){ int k; while(true){ k=tr[x].son[1]; if(!k){ k=++tot; tr[x].son[1]=k; tr[k].val=v; tr[k].fa=x; break; } x=k; } splay(k,0); } int findkth(int k){ int x=rt; while(true){ markdown(x); if(tr[tr[x].son[0]].siz+1==k)return x; else if(tr[tr[x].son[0]].siz>=k)x=tr[x].son[0]; else k-=tr[tr[x].son[0]].siz+1,x=tr[x].son[1]; } } void work(int x,int y){ int a=findkth(x); int b=findkth(y+2); splay(a,0); splay(b,a); tr[tr[b].son[0]].mark^=1; } void print(int p){ markdown(p); if(tr[p].son[0])print(tr[p].son[0]); if(tr[p].val>1&&tr[p].val<n+2)printf("%d ",tr[p].val-1); if(tr[p].son[1])print(tr[p].son[1]); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n+2;i++){ insert(rt,i); } for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); work(x,y); } print(rt); return 0; }