BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊

  1 #include<string.h>
  2 #include<stdlib.h>
  3 #include<stdio.h>
  4 #include<math.h>
  5 //#include<assert.h>
  6 #include<algorithm> 
  7 //#include<iostream>
  8 //#include<bitset>
  9 using namespace std;
 10 
 11 int n,m;
 12 #define maxn 200011
 13 struct LCT
 14 {
 15     struct Node
 16     {
 17         int fa,son[2];
 18         bool rev;
 19         int size,realroot;
 20     }a[maxn];
 21     void makeatree(int id)
 22     {
 23         a[id].fa=a[id].son[0]=a[id].son[1]=a[id].rev=0;
 24         a[id].size=1; a[id].realroot=id;
 25     }
 26     void up(int x)
 27     {
 28         if (!x) return;
 29         int &p=a[x].son[0],&q=a[x].son[1];
 30         a[x].size=a[p].size+a[q].size+1;
 31     }
 32     void revsingle(int x)
 33     {
 34         if (!x) return;
 35         a[x].rev^=1;
 36         int &p=a[x].son[0],&q=a[x].son[1];
 37         p^=q; q^=p; p^=q;
 38     }
 39     void down(int x)
 40     {
 41         int &p=a[x].son[0],&q=a[x].son[1];
 42         if (a[x].rev) {revsingle(p); revsingle(q); a[x].rev=0;}
 43         a[p].realroot=a[q].realroot=a[x].realroot;
 44     }
 45     int sta[maxn];
 46     void download(int x)
 47     {
 48         int top=0,i; for (i=x;!isroot(i);i=a[i].fa) sta[++top]=i; sta[++top]=i;
 49         for (;top;top--) down(sta[top]);
 50     }
 51     bool isroot(int x)
 52     {
 53         if (a[x].fa==0) return 1;
 54         return (a[a[x].fa].son[0]!=x && a[a[x].fa].son[1]!=x);
 55     }
 56     void rotate(int x)
 57     {
 58         const int y=a[x].fa,z=a[y].fa;
 59         bool w=(x==a[y].son[0]);
 60         a[x].fa=z;
 61         if (!isroot(y)) a[z].son[y==a[z].son[1]]=x;
 62         a[y].son[w^1]=a[x].son[w];
 63         if (a[x].son[w]) a[a[x].son[w]].fa=y;
 64         a[x].son[w]=y;
 65         a[y].fa=x;
 66         up(y); up(z);
 67     }
 68     void splay(int x)
 69     {
 70         if (!x) return;
 71         download(x);
 72         while (!isroot(x))
 73         {
 74             const int y=a[x].fa,z=a[y].fa;
 75             if (!isroot(y))
 76             {
 77                 if ((y==a[z].son[0])^(x==a[y].son[0])) rotate(x);
 78                 else rotate(y);
 79             }
 80             rotate(x);
 81         }
 82         up(x);
 83     }
 84     void access(int x)
 85     {
 86         int y=0,tmp=x;
 87         while (x) {splay(x); a[x].son[1]=y; up(x); y=x; x=a[x].fa;}
 88         splay(tmp);
 89     }
 90 //    int findroot(int x)
 91 //    {
 92 //        access(x);
 93 //        int y=x;
 94 //        while (a[y].son[0]) {down(y); y=a[y].son[0];}
 95 //        return y;
 96 //    }
 97     void resetroot(int x)
 98     {
 99         access(x);
100         revsingle(x);
101     }
102     void link(int x,int y)
103     {
104         resetroot(x);
105         a[x].fa=y;
106         a[x].realroot=a[y].realroot;
107     }
108     void cut(int x,int y)
109     {
110         resetroot(x);
111         access(y);
112         a[y].son[0]=a[x].fa=0;
113         up(y); a[x].realroot=x;
114     }
115     int query(int x)
116     {
117         access(x);
118         int y=a[x].realroot;
119         resetroot(y);
120         access(x);
121         return a[a[x].son[0]].size+1;
122     }
123 //    void test()
124 //    {
125 //        for (int i=1;i<=n;i++) cout<<i<<" size"<<a[i].size<<" realroot"<<a[i].realroot<<" rev"
126 //        <<a[i].rev<<" son0 "<<a[i].son[0]<<" son1 "<<a[i].son[1]<<" fa "<<a[i].fa<<endl;
127 //        cout<<endl;
128 //    }
129 }t;
130 
131 int num[maxn];
132 int main()
133 {
134     scanf("%d",&n);
135     for (int i=1;i<=n;i++) t.makeatree(i);
136     for (int i=1;i<=n;i++)
137     {
138         scanf("%d",&num[i]);
139         if (i+num[i]<=n) t.link(i,i+num[i]);
140     }
141     scanf("%d",&m);
142     int x,y,z;
143     while (m--)
144     {
145         scanf("%d%d",&x,&y); y++;
146         if (x==1) printf("%d
",t.query(y));
147         else
148         {
149             scanf("%d",&z);
150             if (y+num[y]<=n) t.cut(y,y+num[y]);
151             num[y]=z;
152             if (y+z<=n) t.link(y,y+z);
153         }
154     }
155     return 0;
156 }