【HYSBZ】2002 Bounce 弹飞绵羊

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #define MAXN 200010
  5 using namespace std;
  6 struct LCT {
  7     int bef[MAXN];
  8     int next[MAXN][2], pre[MAXN], key[MAXN], sum[MAXN];
  9     void Init() {
 10         memset(next, 0, sizeof(next));
 11         memset(pre, 0, sizeof(pre));
 12     }
 13     inline void PushUp(int x) {
 14         sum[x] = key[x] + sum[next[x][0]] + sum[next[x][1]];
 15     }
 16     void Rotate(int x, int kind) {
 17         int y, z;
 18         y = pre[x];
 19         z = pre[y];
 20         next[y][!kind] = next[x][kind];
 21         pre[next[x][kind]] = y;
 22         next[z][next[z][1] == y] = x;
 23         pre[x] = z;
 24         next[x][kind] = y;
 25         pre[y] = x;
 26         PushUp(y);
 27     }
 28     void Splay(int x) {
 29         int rt;
 30         for (rt = x; pre[rt]; rt = pre[rt])
 31             ;
 32         if (rt != x) {
 33             bef[x] = bef[rt];
 34             bef[rt] = 0;
 35             while (pre[x]) {
 36                 if (next[pre[x]][0] == x)
 37                     Rotate(x, 1);
 38                 else
 39                     Rotate(x, 0);
 40             }
 41             PushUp(x);
 42         }
 43     }
 44     void Access(int x) {
 45         int father;
 46         for (father = 0; x; x = bef[x]) {
 47             Splay(x);
 48             bef[next[x][1]] = x;
 49             bef[father] = 0;
 50             pre[next[x][1]] = 0;
 51             next[x][1] = father;
 52             pre[father] = x;
 53             father = x;
 54             PushUp(x);
 55         }
 56     }
 57     int Query(int x) {
 58         Access(x);
 59         Splay(x);
 60         return sum[next[x][0]];
 61     }
 62     void Cut(int x) {
 63         Access(x);
 64         Splay(x);
 65         bef[next[x][0]] = bef[x];
 66         bef[x] = 0;
 67         pre[next[x][0]] = 0;
 68         next[x][0] = 0;
 69     }
 70     void Join(int x, int y) {
 71         Cut(x);
 72         bef[x] = y;
 73     }
 74 } lct;
 75 int K[MAXN];
 76 int INT() {
 77     int res;
 78     char ch;
 79     while (ch = getchar(), !isdigit(ch))
 80         ;
 81     for (res = ch - '0'; ch = getchar(), isdigit(ch);)
 82         res = res * 10 + ch - '0';
 83     return res;
 84 }
 85 int main() {
 86     int n, i;
 87     int q, x, y, cmd;
 88     while (~scanf("%d", &n)) {
 89         lct.Init();
 90         for (i = 1; i <= n; i++) {
 91             K[i] = INT();
 92             if (i + K[i] > n)
 93                 lct.bef[i] = 0;
 94             else
 95                 lct.bef[i] = i + K[i];
 96             lct.key[i] = lct.sum[i] = 1;
 97         }
 98         q = INT();
 99         while (q--) {
100             cmd = INT(), x = INT() + 1;
101             if (cmd == 1)
102                 printf("%d\n", lct.Query(x) + 1);
103             else {
104                 y = INT();
105                 K[x] = y;
106                 if (x + y > n)
107                     y = 0;
108                 else
109                     y = x + y;
110                 lct.Join(x, y);
111             }
112         }
113     }
114     return 0;
115 }