2002: [Hnoi2010]Bounce 弹飞绵羊

https://www.lydsy.com/JudgeOnline/problem.php?id=2002
分析：
　　绵羊在弹飞的路径中相当于一棵树，这棵树需要更改形态，删一条边，加一条边，所以LCT维护一下。
代码：
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 
 5 inline int read() {
 6     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
 7     for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
 8 }
 9 
10 const int N = 200100;
11 int ch[N][2],fa[N],rev[N],val[N],siz[N],sk[N],a[N],Top,n;
12 
13 void pushup(int x) {
14     siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
15 }
16 void pushdown(int x) {
17     if (rev[x]) {
18         rev[ch[x][0]] ^= 1; rev[ch[x][1]] ^= 1;
19         swap(ch[x][0], ch[x][1]);
20         rev[x] ^= 1;
21     }
22 }
23 bool isroot(int x) {
24     return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
25 }
26 int son(int x) {
27     return x == ch[fa[x]][1];
28 }
29 void rotate(int x) {
30     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
31     if (!isroot(y)) ch[z][c] = x;fa[x] = z;
32     ch[x][!b] = y;fa[y] = x;
33     ch[y][b] = a;if (a) fa[a] = y;
34     pushup(y);pushup(x);
35 }
36 void splay(int x) {
37     sk[Top = 1] = x;
38     for (int i=x; !isroot(i); i=fa[i]) sk[++Top] = fa[i];
39     while (Top) pushdown(sk[Top--]);
40     while (!isroot(x)) {
41         int y = fa[x];
42         if (isroot(y)) rotate(x);
43         else {
44             if (son(x) == son(y)) rotate(y), rotate(x);
45             else rotate(x), rotate(x);
46         }
47     }
48 }
49 void access(int x) {
50     for (int last=0; x; last=x, x=fa[x]) {
51         splay(x); ch[x][1] = last; pushup(x);
52     }
53 }
54 void makeroot(int x) {
55     access(x); splay(x); rev[x] ^= 1;
56 }
57 int find(int x) {
58     access(x); splay(x); 
59     while (ch[x][0]) x = ch[x][0];
60     return x;
61 }
62 void link(int x,int y) {
63     makeroot(x); 
64     fa[x] = y;
65 }
66 void cut(int x,int y) {
67     makeroot(x); access(y); splay(y);
68     if (fa[x] == y && !ch[x][1]) fa[x] = ch[y][0] = 0;
69 }
70 
71 void query() {
72     makeroot(n + 1);
73     int p = read() + 1;
74     access(p);
75     splay(p);
76     printf("%d
",siz[p] - 1);
77 }
78 void change() {
79     int p = read() + 1,x = read(),t = p+x > n+1 ? n+1: p+x; // --- 判断是否大于n+1，不判luogu上80 
80     cut(p,a[p]);
81     a[p] = t;
82     link(p,a[p]);
83 }
84 
85 int main() {
86     n = read();
87     for (int i=1; i<=n; ++i) {
88         a[i] = i + read();
89         a[i] = a[i] > n+1 ? n+1 : a[i];
90     }
91     for (int i=1; i<=n; ++i) link(i,a[i]);
92     int m = read();
93     while (m--) {
94         int opt = read();
95         if (opt == 1) query();
96         else change();
97     }
98     return 0;
99 }