BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊（动态树LCT）

2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 2843 Solved: 1519
[Submit][Status]

Description

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

Input

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

Output

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

Sample Input

4
1 2 1 1
3
1 1
2 1 1
1 1

Sample Output

2
3

HINT

Source

Splay 启发式合并

动态树，形成一颗树。

改变树的边，然后维护子树大小就可以了

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013-9-4 7:41:21
  4 File Name     :BZOJ2002弹飞绵羊.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 
 21 const int MAXN = 200010;
 22 int ch[MAXN][2],pre[MAXN];
 23 int size[MAXN];
 24 bool rt[MAXN];
 25 void push_down(int r)
 26 {
 27     
 28 }
 29 void push_up(int r)
 30 {
 31     size[r] = size[ch[r][0]] + size[ch[r][1]] + 1;
 32 }
 33 void Rotate(int x)
 34 {
 35     int y = pre[x], kind = ch[y][1]==x;
 36     ch[y][kind] = ch[x][!kind];
 37     pre[ch[y][kind]] = y;
 38     pre[x] = pre[y];
 39     pre[y] = x;
 40     ch[x][!kind] = y;
 41     if(rt[y])
 42         rt[y] = false, rt[x] = true;
 43     else
 44         ch[pre[x]][ch[pre[x]][1]==y] = x;
 45     push_up(y);
 46 }
 47 void P(int r)
 48 {
 49     if(!rt[r])P(pre[r]);
 50     push_down(r);
 51 }
 52 void Splay(int r)
 53 {
 54     P(r);
 55     while( !rt[r] )
 56     {
 57         int f = pre[r], ff = pre[f];
 58         if(rt[f])
 59             Rotate(r);
 60         else if( (ch[ff][1]==f)==(ch[f][1]==r) )
 61             Rotate(f), Rotate(r);
 62         else
 63             Rotate(r), Rotate(r);
 64     }
 65     push_up(r);
 66 }
 67 int Access(int x)
 68 {
 69     int y = 0;
 70     for( ; x ; x = pre[y=x])
 71     {
 72         Splay(x);
 73         rt[ch[x][1]] = true, rt[ch[x][1]=y] = false;
 74         push_up(x);
 75     }
 76     return y;
 77 }
 78 int a[MAXN];
 79 int main()
 80 {
 81     //freopen("in.txt","r",stdin);
 82     //freopen("out.txt","w",stdout);
 83     
 84     int n,m;
 85     while(scanf("%d",&n) == 1)
 86     {
 87         for(int i = 1;i <= n;i++)
 88             scanf("%d",&a[i]);
 89         for(int i = 0;i <= n+1;i++)
 90         {
 91             pre[i] = 0;
 92             ch[i][0] = ch[i][1] = 0;
 93             rt[i] = true;
 94             size[i] = 1;
 95         }
 96         size[0] = 0;
 97         for(int i = 1;i <= n;i++)
 98         {
 99             int t = i + a[i];
100             if( t > n+1) t = n+1;
101             pre[i] = t;
102         }
103         int op;
104         int u,v;
105         scanf("%d",&m);
106         while(m--)
107         {
108             scanf("%d",&op);
109             if(op == 1)
110             {
111                 scanf("%d",&u);
112                 u++;
113                 Access(u);
114                 Splay(u);
115                 printf("%d
",size[ch[u][0]]);
116             }
117             else
118             {
119                 scanf("%d%d",&u,&v);
120                 u++;
121                 Access(u);
122                 Splay(u);
123                 pre[ch[u][0]] = pre[u];
124                 pre[u] = 0;
125                 rt[ch[u][0]] = true;
126                 ch[u][0] = 0;
127                 push_up(u);
128                 int t = u + v;
129                 if(t > n+1) t = n+1;
130                 pre[u] = t;
131             }
132         }
133     }
134     return 0;
135 }