【BZOJ1180】: [CROATIAN2009]OTOCI & 2843: 极地旅行社 LCT

  1 #include <iostream>
  2 #include <cstdio>
  3 #define N 300030
  4 using namespace std;
  5 int n,m;
  6 struct node
  7 {
  8     node *fa,*ch[2];
  9     int data,sum;
 10     bool rev;
 11     node(int x);
 12     bool chr() {return this==fa->ch[1];}
 13     bool isrt() {return this!=fa->ch[1] && this!=fa->ch[0];}
 14     void push_up() {sum=ch[0]->sum+ch[1]->sum+data;}
 15     void setc(node *x,int t) {this->ch[t]=x; x->fa=this;}
 16     void push_down()
 17     {
 18         if (!isrt()) fa->push_down();
 19         if (rev)
 20         {
 21             ch[0]->rev^=1;
 22             ch[1]->rev^=1;
 23             swap(ch[0],ch[1]);
 24             rev=0;
 25         }
 26     }
 27 }*null=new node(0),*lct[N];
 28 node::node (int x) {fa=ch[0]=ch[1]=null; data=sum=x; rev=0;}
 29 inline int read()
 30 {
 31     char c;
 32     int ans=0,f=1;
 33     while (!isdigit(c=getchar())) {if (c==‘-‘) f=-1;}
 34     ans=c-‘0‘;
 35     while (isdigit(c=getchar())) ans=ans*10+c-‘0‘;
 36     return ans*f;
 37 }
 38 namespace LCT 
 39 {
 40     void rotate(node *x)
 41     {
 42         node *r=x->fa;
 43         if (x==null || r==null) return;
 44         int t=x->chr();
 45         //x->push_down();r->push_down();
 46         if (r->isrt()) x->fa=r->fa;
 47         else r->fa->setc(x,r->chr());
 48         r->setc(x->ch[t^1],t);
 49         x->setc(r,!t);
 50         x->push_up(); r->push_up();
 51     }
 52     void Splay(node *x)
 53     {
 54         x->push_down();
 55         for (;!x->isrt();rotate(x))
 56             if (!x->fa->isrt())
 57                 if (x->chr()==x->fa->chr())    rotate(x->fa);
 58                 else rotate(x);
 59         x->push_up();
 60     }
 61     void Access(node *x)
 62     {
 63         node *r=null;
 64         for (;x!=null;r=x,x=x->fa)
 65         {
 66             Splay(x);
 67             x->ch[1]=r;
 68         }
 69     }
 70     void MakeRoot(node *x)
 71     {
 72         Access(x);
 73         Splay(x);
 74         x->rev^=1;
 75     }
 76     void Link(node *x,node *y)
 77     {
 78         MakeRoot(x);
 79         x->fa=y;
 80     }
 81     void Cut(node *x,node *y)
 82     {
 83         MakeRoot(x);
 84         Access(y); Splay(y);
 85         y->ch[0]->fa=null; y->ch[0]=null;
 86     }
 87     node *Find(node *x)
 88     {
 89         Access(x); Splay(x);
 90         while (x->ch[0]!=null) x=x->ch[0];
 91         return x;
 92     }
 93     void Change(node *x,int v)
 94     {
 95         x->push_down();
 96         Splay(x);
 97         x->data=v;
 98         x->push_up();
 99     }
100     int Query(node *x,node *y)
101     {
102         MakeRoot(x);
103         Access(y); Splay(y);
104         return y->sum;
105     }
106 }
107 using namespace LCT;
108 int main()
109 {
110     char s[20];
111     int x,y;
112     n=read();
113     for (int i=1;i<=n;i++)  x=read(),lct[i]=new node(x);
114     m=read();
115     for (int i=1;i<=m;i++)
116     {
117         scanf("%s",s); x=read(); y=read();
118         if (s[0]==‘b‘) if (Find(lct[x])!=Find(lct[y])) printf("yes\n"),Link(lct[x],lct[y]);
119                         else printf("no\n"); 
120         if (s[0]==‘p‘) Change(lct[x],y);
121         if (s[0]==‘e‘) if (Find(lct[x])==Find(lct[y])) printf("%d\n",Query(lct[x],lct[y]));
122                         else printf("impossible\n"); 
123     }
124     return 0;
125 }