1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #define KT ch[ch[root][1]][0]  6 #define LC ch[x][0]  7 #define RC ch[x][1]  8 #define N 310001  9 using namespace std; 10  11 struct SplayTree{ 12     int root; 13     int fa[N]; 14     int ch[N][2]; 15     int sz[N]; 16     int top1; 17     int top2; 18     int ss[N]; 19     int que[N]; 20  21  22     void rotate(int x,bool f){ 23         int y=fa[x]; 24         int z=fa[y]; 25         pushdown(y); 26         pushdown(x); 27         ch[y][!f]=ch[x][f]; 28         fa[ch[x][f]]=y; 29         fa[x]=z; 30         if (z) { 31             ch[z][ch[z][1]==y] = x; 32         } 33         ch[x][f] = y; 34         fa[y]=x; 35         pushup(y); 36     } 37     void splay(int x, int g) { 38         int y = fa[x]; 39         pushdown(x); 40         while(y!=g){ 41             int z= fa[y]; 42             bool f = (ch[y][0]==x); 43             if(z != g && f == (ch[z][0]==y)){ 44                 rotate(y,f); 45             } 46             rotate(x,f); 47             y=fa[x]; 48         } 49         pushup(x); 50         if(g==0) root = x; 51     } 52     void rotateTo(int k,int g) { 53         int x=root; 54         pushdown(x); 55         while(sz[LC] != k){ 56             if(k<sz[LC]){ 57                 x=LC; 58             }else{ 59                 k -= sz[LC] + 1; 60                 x = RC; 61             } 62             pushdown(x); 63         } 64         splay(x,g); 65     } 66     void build(int l,int r,int f){ 67         if(l>r){ 68             return ; 69         } 70         int x = (l + r) >> 1; 71         LC = (x - 1 >= l)? (x - 1 + l)>> 1 :0; 72         RC = (r >= x + 1)? (x + 1 + r)>> 1 :0; 73         fa[x] = f; 74         build(l,x - 1,x); 75         build(x + 1,r,x); 76         pushup(x); 77     } 78     void erase(int x){ 79         if(x==0) 80             return; 81         int father= fa[x]; 82         int head = 0, tail=0; 83         for(que[tail++] =x ; head < tail; head++){ 84             ss[top2++] = que[head]; 85             if(ch[que[head]][0]){ 86                 que[tail++]=ch[que[head]][0]; 87             } 88             if(ch[que[head]][1]){ 89                 que[tail++] = ch[que[head]][1]; 90             } 91         } 92         ch[father][ch[father][1]==x]=0; 93         pushup(father); 94     } 95     void makeTree(int &x, int l, int r, int f){ 96         if(l > r){ 97             return; 98         } 99         int m=(l+r)>>1;100         newNode(x, m);101         makeTree(LC,l,m-1,x);102         makeTree(RC,m+1,r,x);103         fa[x]=f;104         pushup(x);105     }106     void treaval(int x){107         if (x) {108             pushdown(x);109             treaval(LC);110             //printf("@%d",val[x]);111             ans[cnt++]=val[x];112             treaval(RC);113         }114     }115 116     void newNode(int &x,int c){117         if(top2){118             x = ss[--top2];119         } else {120             x = ++top1;121         }122         LC = RC = fa[x] =0;123         sz[x] = 1;124     }125     void pushdown(int x){126 127     }128     void pushup(int x){129         sz[x]=1+sz[LC]+sz[RC];130     }131 132     void debug(){133         treaval(root);134         cout<<endl;135     }136     void cutTo(int l,int r,int c){137         rotateTo(l-1,0);138         rotateTo(r+1,root);139         int tmp=KT;140         KT=0;141         pushup(ch[root][1]);142         pushup(root);143 144         rotateTo(c,0);145         rotateTo(c+1,root);146         fa[tmp]=ch[root][1];147         KT=tmp;148         pushup(ch[root][1]);149         pushup(root);150     }151 152     void init(int n){153 154         top1=top2=root=0;155         newNode(root,0);156         newNode(ch[root][1],0);157         fa[ch[root][1]]=root;158         //for(int i=1;i<=n;i++)scanf("%d",&num[i]);159         makeTree(KT,1,n,ch[root][1]);160         pushup(ch[root][1]);161         pushup(root);162     }163     void solve(int n,int m){164 165     }166 167 }spt;