HDU3487(splay区间翻转+区间切割）(二)
; push_up(ch[root][1]); push_up(root); } int Get_max(int x){ push_down(x); while(ch[x][1]){ x=ch[x][1]; push_down(x); } return x; } void merge(int root1,int root2)/*root2接到root1右子树，要求root1无右子树*/ { ch[root1][1]=root2; pre[root2]=root1; } int __; void travel(int x){ if(!x)return; push_down(x); travel(ch[x][0]); ans[__++]=key[x]; travel(ch[x][1]); } int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ if(n<0&&m<0)return 0; init(n); char op[10]; int L,R,C; while(m--){ scanf("%s%d%d",op,&L,&R); if(op[0]=='F'){ Splay(Get_kth(root,L),0); Splay(Get_kth(root,R+2),root); Modify(ch[ch[root][1]][0]); }else{ scanf("%d",&C); Splay(Get_kth(root,L),0); Splay(Get_kth(root,R+2),root); int root1=ch[ch[root][1]][0];/*删除区间[L,R]*/ ch[ch[root][1]][0]=0; push_up(ch[root][1]); push_up(root); Splay(Get_kth(root,C+1),0);/*先分裂区间C两边，插入区间[L,R]，然后合并*/ int root2=ch[root][1]; merge(root,root1); push_up(root); Splay(Get_max(root),0); merge(root,root2); push_up(root); } } __=0; travel(root); rep(i,1,n)printf("%d%c",ans[i],i==n?'\n':' '); } return 0; }