http://acm.hdu.edu.cn/showproblem.php?pid=3487
提取一段区间,插入到另一个位置,只要写好了关键的三个函数就很轻松了
/* 区间翻转,注意标记的下传 */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define L ch[x][0] #define R ch[x][1] #define KT (ch[ ch[rt][1] ][0]) const int maxn = 300010; struct SplayTree { int sz[maxn]; int ch[maxn][2]; int pre[maxn]; int rt,top; inline void down(int x){ if(flip[x]) { flip[ L ] ^= 1; flip[ R ] ^= 1; swap(L,R); flip[x]=0; } } inline void up(int x){ sz[x]=1+sz[ L ] + sz[ R ]; } inline void Rotate(int x,int f){ int y=pre[x]; down(y); down(x); ch[y][!f] = ch[x][f]; pre[ ch[x][f] ] = y; pre[x] = pre[y]; if(pre[x]) ch[ pre[y] ][ ch[pre[y]][1] == y ] =x; ch[x][f] = y; pre[y] = x; up(y); } inline void Splay(int x,int goal){//将x旋转到goal的下面 down(x);//防止pre[x]就是目标点,下面的循环就进不去了,x的信息就传不下去了 while(pre[x] != goal){ down(pre[pre[x]]); down(pre[x]);down(x);//在旋转之前需要先下传标记,因为节点的位置可能会发生改变 if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][0] == x); else { int y=pre[x],z=pre[y]; int f = (ch[z][0]==y); if(ch[y][f] == x) Rotate(x,!f),Rotate(x,f); else Rotate(y,f),Rotate(x,f); } } up(x); if(goal==0) rt=x; } inline void RTO(int k,int goal){//将第k位数旋转到goal的下面 int x=rt; down(x); while(sz[ L ]+1 != k) { if(k < sz[ L ] + 1 ) x=L; else { k-=(sz[ L ]+1); x = R; } down(x); } Splay(x,goal); } void vist(int x){ if(x){ printf("结点%2d : 左儿子 %2d 右儿子 %2d %2d flip:%d\n",x,L,R,val[x],flip[x]); vist(L); vist(R); } } void Newnode(int &x,int c,int f){ x=++top; L = R = 0; pre[x]=f; sz[x]=1; val[x]=c; flip[x]=0; } inline void build(int &x,int l,int r,int f){ if(l>r) return ; int m=l+r>>1; Newnode(x,m,f); build(L , l , m-1 , x); build(R , m+1 , r , x); pre[x]=f; up(x); } inline void init(int n){ ch[0][0]=ch[0][1]=pre[0]=sz[0]=0; rt=top=0; flip[0]=0; val[0]=0; Newnode(rt,-1,0); Newnode(ch[rt][1],-1,rt); sz[rt]=2; build(KT,1,n,ch[rt][1]); // vist(rt); } void print(int x) { if(x) { down(x); print(L); if(val[x]!=-1) { if(flag) printf(" "); printf("%d",val[x]); flag=1; } print(R); } } void OUT() { flag=0; print(rt); printf("\n"); } void gao1(int l,int r,int c) { RTO(l-1+1,0); RTO(r+1+1,rt); int tmp=KT; KT=0; up(ch[rt][1]); up(rt); RTO(c+1,0); RTO(c+1+1,rt); KT=tmp; pre[tmp]=ch[rt][1]; up(ch[rt][1]); up(rt); } void gao2(int l,int r) { RTO(l-1+1,0); RTO(r+1+1,rt); flip[KT] ^= 1; } int flag; int flip[maxn]; int val[maxn]; }spt; int main() { char op[10]; int n,m,a,b,c; while(scanf("%d%d",&n,&m)!=EOF){ if(n==-1 && m==-1) break; spt.init(n); for(int i=1;i<=m;i++) { scanf("%s",op); if(op[0]=='C') { scanf("%d%d%d",&a,&b,&c); spt.gao1(a,b,c); } else { scanf("%d%d",&a,&b); spt.gao2(a,b); } } spt.OUT(); } return 0; }