1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 300010 12 #define LL long long 13 #define INF 0xfffffff 14 #define key_value ch[ch[root][1]][0] 15 const double eps = 1e-8; 16 const double pi = acos(-1.0); 17 const double inf = ~0u>>2; 18 using namespace std; 19 struct splay_tree 20 { 21     int pre[N],size[N]; 22     int ch[N][2]; 23     int root,tot,num,tot1; 24     int key[N],lz[N]; 25     void dfs(int x) 26     { 27         if(x) 28         { 29             dfs(ch[x][0]); 30             printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,key=%2d lz = %d\n", 31                    x,ch[x][0],ch[x][1],pre[x],size[x],key[x],lz[x]); 32             dfs(ch[x][1]); 33         } 34     } 35     void debug() 36     { 37         printf("root:%d\n",root); 38         dfs(root); 39     } 40 //以上用于debug*/ 41     void newnode(int &x,int v,int fa)//新建一结点 42     { 43         x = ++tot; 44         ch[x][0]=ch[x][1] = 0; 45         pre[x] = fa; 46         lz[x] = 0; 47         size[x] = 1; 48         key[x] = v; 49     } 50     void pushdown(int w) 51     { 52         if(lz[w]) 53         { 54             int l = ch[w][0],r = ch[w][1]; 55             swap(ch[w][0],ch[w][1]); 56  57             lz[l]^=lz[w]; 58             lz[r]^=lz[w]; 59             lz[w] = 0; 60         } 61     } 62     void pushup(int w)//由儿子更新其父亲 63     { 64         size[w] = size[ch[w][0]]+size[ch[w][1]]+1; 65         //cout<<s[w][0]<<" "<<s[w][1]<<endl; 66     } 67     void rotate(int r,int kind)//旋转操作，根据kind进行左旋和右旋 68     { 69         int y = pre[r]; 70         pushdown(y); 71         pushdown(r); 72         ch[y][!kind] = ch[r][kind]; 73         pre[ch[r][kind]] = y; 74         if(pre[y]) 75         { 76             ch[pre[y]][ch[pre[y]][1]==y] = r; 77         } 78         pre[r] = pre[y]; 79         ch[r][kind] = y; 80         pre[y] = r; 81         pushup(y); 82         pushup(r); 83     } 84     void splay(int r,int goal)//将r结点旋至goal下 85     { 86         pushdown(r); 87         while(pre[r]!=goal) 88         { 89             if(pre[pre[r]]==goal) 90             { 91                 rotate(r,ch[pre[r]][0]==r); 92             } 93             else 94             { 95                 int y = pre[r]; 96                 int kind = (ch[pre[y]][0]==y); 97                 if(ch[y][kind]==r) 98                 { 99                     rotate(r,!kind);100                     rotate(r,kind);101                 }102                 else103                 {104                     rotate(y,kind);105                     rotate(r,kind);106                 }107             }108         }109         pushup(r);110         if(goal==0) root = r;111     }112     int get_k(int k)//得到第k个的结点113     {114         int r = root;115        pushdown(r);116         while(size[ch[r][0]]+1!=k)117         {118             if(size[ch[r][0]]>=k)119                 r = ch[r][0];120             else121             {122                 k-=(size[ch[r][0]]+1);//根据左右结点的数量来确定第k个节点在哪里123                 r = ch[r][1];124             }125             pushdown(r);126         }127         pushup(r);128         return r;129     }130     void cut(int l,int r,int k)131     {132         splay(get_k(l),0);133         splay(get_k(r+2),root);134         pushdown(ch[root][1]);135         int nod = key_value;136         ch[ch[root][1]][0] = 0;137         pre[nod] = 0;138         pushup(ch[root][1]);139         pushup(root);140         //debug();141         splay(get_k(k),0);142         splay(get_k(k+1),root);143         ch[ch[root][1]][0] = nod;144         pre[nod] = ch[root][1];145         pushup(ch[root][1]);146         pushup(root);147        // debug();148     }149     void filp(int l,int r)150     {151         //cout<<get_k(l)<<" "<<get_k(r+2)<<endl;152         splay(get_k(l),0);153         splay(get_k(r+2),root); //cout<<","<<endl;debug();154         lz[key_value]^=1;155         //swap(ch[key_value][0],ch[key_value][1]);156         pushup(ch[root][1]);157         pushup(root);158     }159     void work(int n)160     {161         int i;162         for(i = 1 ;i < n ;i++)163         {164             printf("%d ",key[get_k(i+1)]);165         }166         printf("%d\n",key[get_k(n+1)]);167         //debug();168     }169     void build(int &x,int l,int r,int fa)170     {171         int m = (l+r)>>1;172         if(l>r) return ;173         newnode(x,m,fa);174         build(ch[x][0],l,m-1,x);175         build(ch[x][1],m+1,r,x);176         pushup(x);177     }178     void init(int o)179     {180         size[0] = ch[0][0] = ch[0][1] =  key[0] = lz[0] = 0;181         root = tot = 0;182         newnode(root,0,0);183         newnode(ch[root][1],0,root);184         build(ch[ch[root][1]][0],1,o,ch[root][1]);185         size[root] = 2;186         pushup(ch[root][1]);187         pushup(root);188     }189 }SP;190 int main()191 {192     int n,q;193     while(scanf("%d%d",&n,&q)!=EOF)194     {195         if(n==-1&&q==-1) break;196         SP.init(n);197         while(q--)198         {199             char sq[20];200             int k,x,y;201             scanf("%s",sq);202             if(sq[0]==‘C‘)203             {204                 scanf("%d%d%d",&x,&y,&k);205                 SP.cut(x,y,k+1);206               // SP.debug();207 //                SP.work(n);208             }209             else210             {211                 //SP.debug();212                 scanf("%d%d",&x,&y);213                 SP.filp(x,y);214                 //SP.debug();215             }216             //SP.work(n);217         }218         SP.work(n);219     }220     return 0;221 }