hdu3487Play with Chain(splay)

  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                 else
103                 {
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             else
121             {
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             else
210             {
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 }