脑洞大开加偏执人格——可持久化treap版的Link Cut Tree2

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 int father[10010];
  8 struct node
  9 {
 10     int num;
 11     int key;
 12     int left;
 13     int right;
 14     node* ls;
 15     node* rs;
 16     bool turn;
 17     node* f;
 18     node()
 19     {
 20         key=rand();
 21         f=NULL;
 22     }
 23 }no[10010];
 24 
 25 int root;
 26 
 27 void swap(node** a,node** b)
 28 {
 29     node* c=*a;
 30     *a=*b;
 31     *b=c;
 32 }
 33 
 34 void swap(int* a,int *b)
 35 {
 36     int c=*a;
 37     *a=*b;
 38     *b=c;
 39 }
 40 
 41 void pushdown(node* now)
 42 {
 43     if (now->turn)
 44     {
 45         swap(&now->ls,&now->rs);
 46         if (now->ls)
 47         {
 48             now->ls->turn=!now->ls->turn;    
 49             swap(&now->ls->left,&now->ls->right);
 50         }
 51         if (now->rs)
 52         {
 53             now->rs->turn=!now->rs->turn;
 54             swap(&now->rs->left,&now->rs->right);
 55         }
 56     }
 57     now->turn=false;
 58 }
 59 
 60 void update(node* now)
 61 {
 62     now->left=now->right=now->num;
 63     if (now->ls)
 64     {
 65         now->left=now->ls->left;
 66         now->ls->f=now;
 67     }
 68     if (now->rs)
 69     {
 70         now->right=now->rs->right;
 71         now->rs->f=now;
 72     }
 73 }
 74 
 75 node* merge(node* a,node* b)
 76 {
 77     if (!a) {update(b);return b;}
 78     if (!b) {update(a);return a;}
 79     pushdown(a);
 80     pushdown(b);
 81     if (a->key<b->key)
 82     {
 83         a->rs=merge(a->rs,b);
 84         a->rs->f=a;
 85         update(a);
 86         return a;
 87     }
 88     else
 89     {
 90         b->ls=merge(a,b->ls);
 91         b->ls->f=b;
 92         update(b);
 93         return b;
 94     }
 95 }
 96 
 97 struct nodepair 
 98 {
 99     node* l;
100     node* r;
101 
102     nodepair(node* a,node* b)
103     {
104         l=a;
105         r=b;
106     }
107 };
108 
109 bool Ro[30010];
110 int fi=1;
111 
112 int findroot(int num)
113 {
114     node* now=&no[num];
115     while (now->f)
116     {
117         if (now->f->ls==now) Ro[fi++]=true;
118         else
119             Ro[fi++]=false;
120         now=now->f;
121     }
122     return now->num;
123 }
124 
125 nodepair split(node* now,int dep)
126 {
127     if (dep==0)
128     {
129         pushdown(now);
130         nodepair ret(now,now->rs);
131         if (now->rs)
132         {
133             now->rs->f=NULL;
134             now->rs=NULL;
135         }
136         now->f=NULL;
137         update(now);
138         return ret;
139     }
140     if (now->turn) Ro[dep]=!Ro[dep];
141     pushdown(now);
142     if (Ro[dep])
143     {
144         nodepair km=split(now->ls,dep-1);
145         now->ls=km.r;
146         update(now);
147         now->f=NULL;
148         return nodepair(km.l,now);
149     }
150     else
151     {
152         nodepair km=split(now->rs,dep-1);
153         now->rs=km.l;
154         update(now);
155         now->f=NULL;
156         return nodepair(now,km.r);
157     }
158 }
159 
160 nodepair split(int num)
161 {
162     fi=1;
163     int root=findroot(num);
164     return split(&no[root],fi-1);
165 }
166 
167 node* access(int num)
168 {
169     int now=num;
170     node* lasttree=NULL;
171     while (now!=0)
172     {
173         nodepair km=split(now);
174         if (lasttree)
175             father[lasttree->left]=0;
176         lasttree = merge(km.l,lasttree);
177         if (km.r)    
178             father[km.r->left]=now;
179         now=father[lasttree->left];
180     }
181     return lasttree;
182 }
183 
184 bool query(int x,int y)
185 {
186     int k1=access(x)->left;
187     int k2=access(y)->left;
188     return k1==k2;
189 }
190 
191 void changeroot(int n)
192 {
193     node* road=access(n);
194     road->turn=!road->turn;
195     swap(&road->left,&road->right);
196 }
197 
198 void Connect(int x,int y)
199 {
200     changeroot(y);
201     access(x);
202     father[y]=x;
203 }
204 
205 void destroy(int x,int y)
206 {
207     changeroot(x);
208     access(x);
209     father[y]=0;
210 }
211 
212 int main()
213 {
214     int n;
215     cin>>n;
216     for (int i=1;i<=n;++i)
217     {
218         no[i].num=i;
219         father[i]=0;
220     }
221     int q;
222     char cmd[10];
223     scanf("%d",&q);
224     for (int i=1;i<=q;++i)
225     {
226         int j,k;
227         scanf("%s%d%d",cmd,&j,&k);
228         if (cmd[0]==‘C‘)
229         {
230             Connect(j,k);
231         }
232         if (cmd[0]==‘Q‘)
233         {
234             if (query(j,k))
235                 printf("Yes\n");
236             else
237                 printf("No\n");
238         }
239         if (cmd[0]==‘D‘)
240         {
241             destroy(j,k);
242         }
243     }
244     return 0;
245 }