bzoj2002: [Hnoi2010]Bounce 弹飞绵羊

地址：http://acm.split.hdu.edu.cn/status.php?first=&pid=&user=Honor&lang=0&status=0

题目：

2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 11931 Solved: 6028
[Submit][Status][Discuss]

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

思路：

　　把ｉ和min(n,i+ki)连边，对于询问x，就是求x到n的链长，所以makeroot(n),access(x),splay(x)，输出sz[x]即可。

  1 /**************************************************************
  2     Problem: 2002
  3     User: weeping
  4     Language: C++
  5     Result: Accepted
  6     Time:2308 ms
  7     Memory:6768 kb
  8 ****************************************************************/
  9  
 10 #include <bits/stdc++.h>
 11  
 12 using namespace std;
 13  
 14 struct Link_Cut_Tree
 15 {
 16     static const int MAXN = 200000 + 7;
 17  
 18     int ch[MAXN][2], fa[MAXN], rev[MAXN], sz[MAXN];
 19     int sk[MAXN];
 20  
 21     bool isroot(int x)
 22     {
 23         return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
 24     }
 25  
 26     void reverse(int x)
 27     {
 28         rev[x] ^= 1, swap(ch[x][0],ch[x][1]);
 29     }
 30  
 31     void update(int x)
 32     {
 33         sz[x] = sz[ch[x][0]] +  sz[ch[x][1]] + 1;
 34     }
 35  
 36     void push_down(int x)
 37     {
 38         if(!rev[x]) return ;
 39         if(ch[x][0]) reverse(ch[x][0]);
 40         if(ch[x][1]) reverse(ch[x][1]);
 41         rev[x]=0;
 42     }
 43  
 44     void rotate(int x)
 45     {
 46         int f = fa[x], gf = fa[f];
 47         int t1 = ( x != ch[f][0]), t2 = ( f != ch[gf][0]), tmp = ch[x][1^t1];
 48         if(!isroot(f)) ch[gf][0^t2] = x;
 49         fa[tmp] = f, fa[x] = gf, ch[x][1^t1] = f, fa[f] = x, ch[f][0^t1] = tmp;
 50         update(f);
 51     }
 52  
 53     void splay(int x)
 54     {
 55         int top = 0;
 56         sk[++top] = x;
 57         for(int i = x; !isroot(i); i = fa[i])   sk[++top] = fa[i];
 58         while(top)  push_down(sk[top--]);
 59         for(int f = fa[x], gf = fa[f]; !isroot(x); rotate(x), f = fa[x],gf = fa[f])
 60         if(!isroot(f))
 61             rotate((x==ch[f][0]) ^ (f==ch[gf][0]) ? x : f);
 62         update(x);
 63     }
 64  
 65     void access(int x)
 66     {
 67         for(int p = 0; x; p = x, x = fa[x])
 68             splay(x), ch[x][1] = p, update(x);
 69     }
 70  
 71     void makeroot(int x)
 72     {
 73         access(x), splay(x), reverse(x);
 74     }
 75  
 76     int findroot(int x)
 77     {
 78         access(x), splay(x);
 79         while(ch[x][0]) x = ch[x][0];
 80         return x;
 81     }
 82     void link(int x,int y)
 83     {
 84         makeroot(x), fa[x] = y;
 85     }
 86  
 87     void cut(int x,int y)
 88     {
 89         makeroot(x), access(y), splay(y);
 90         if(ch[y][0] == x)   ch[y][0] = fa[x] = 0;
 91         update(y);
 92     }
 93  
 94     void debug(void)
 95     {
 96         for(int i=1;i<=5;i++)
 97             printf("%d %d %d %d %d %d
",i,fa[i],ch[i][0],ch[i][1],rev[i],sz[i]);
 98     }
 99  
100 }lct;
101  
102 int a[200005];
103 char ss[100];
104 int main(void)
105 {
106     int n,m;
107     cin>>n;
108     for(int i=1;i<=n;i++)   lct.sz[i]=1;
109     for(int i=1;i<=n;i++)
110     {
111         scanf("%d",a+i);
112         if(a[i]+i>n+1)  a[i]=n+1-i;
113         lct.link(i,a[i]+i);
114     }
115     cin>>m;
116     int op,x,y;
117     while(m--)
118     {
119         scanf("%d%d",&op,&x);
120         x++;
121         if(op==1)
122             lct.makeroot(n+1),lct.access(x),lct.splay(x),printf("%d
",lct.sz[x]-1);
123         else
124         {
125             scanf("%d",&y);
126             if(x+y>n+1) y=n+1-x;
127             lct.cut(x,x+a[x]),a[x]=y,lct.link(x,a[x]+x);
128         }
129     }
130     return 0;
131 }
132