2002: [Hnoi2010]Bounce 弹飞绵羊

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

入门级link-cut-tree

跟树链剖分很像，不过树链剖分形态不能变，直接把链分好了，然后用线段树维护这些链

这个link-cut-tree的主要操作是access(x)，表示访问x节点

规则是每次访问x后从x到根节点的路径变成一条链，把这条链上长出来的枝叶减掉，链在不断地变化，所以用splay维护这个链

对于这个改变父节点，就是先断开他与父节点的链，然后接上他现在的父节点

这个讲的比较详细，可以看一下，http://hi.baidu.com/niyuzheno1/item/30994f43ba02c8c31e19bc28

  1 const
  2     maxn=200010;
  3 type
  4     node=record
  5       son:array[0..1]of longint;
  6       size,fa:longint;
  7       root:boolean;
  8     end;
  9 var
 10     tree:array[0..maxn]of node;
 11     n,m:longint;
 12 
 13 procedure rotate(x,w:longint);
 14 var
 15     y:longint;
 16 begin
 17     y:=tree[x].fa;
 18     tree[y].son[w]:=tree[x].son[w xor 1];
 19     if tree[x].son[w xor 1]<>0 then tree[tree[x].son[w xor 1]].fa:=y;
 20     tree[x].son[w xor 1]:=y;
 21     if tree[y].root then
 22       begin
 23         tree[y].root:=false;
 24         tree[x].root:=true;
 25       end
 26     else
 27       if tree[tree[y].fa].son[0]=y then tree[tree[y].fa].son[0]:=x
 28       else tree[tree[y].fa].son[1]:=x;
 29     tree[x].fa:=tree[y].fa;
 30     tree[y].fa:=x;
 31     tree[y].size:=tree[tree[y].son[0]].size+tree[tree[y].son[1]].size+1;
 32 end;
 33 
 34 procedure splay(x:longint);
 35 var
 36     y:longint;
 37 begin
 38     while tree[x].root=false do
 39       begin
 40         y:=tree[x].fa;
 41         if tree[y].root then
 42           if tree[y].son[0]=x then rotate(x,0)
 43           else rotate(x,1)
 44         else
 45           if tree[tree[y].fa].son[0]=y then
 46             if tree[y].son[0]=x then
 47               begin
 48                 rotate(y,0);
 49                 rotate(x,0);
 50               end
 51             else
 52               begin
 53                 rotate(x,1);
 54                 rotate(x,0);
 55               end
 56           else
 57             if tree[y].son[0]=x then
 58               begin
 59                 rotate(x,0);
 60                 rotate(x,1);
 61               end
 62             else
 63               begin
 64                 rotate(y,1);
 65                 rotate(x,1);
 66               end;
 67       end;
 68     tree[x].size:=tree[tree[x].son[0]].size+tree[tree[x].son[1]].size+1;
 69 end;
 70 
 71 procedure access(x:longint);
 72 var
 73     z:longint;
 74 begin
 75     splay(x);
 76     while tree[x].fa<>0 do
 77       begin
 78         z:=tree[x].fa;
 79         splay(z);
 80         tree[tree[z].son[1]].root:=true;
 81         tree[x].root:=false;
 82         tree[z].son[1]:=x;
 83         tree[z].size:=tree[tree[z].son[0]].size+tree[tree[z].son[1]].size+1;
 84         splay(x);
 85       end;
 86 end;
 87 
 88 procedure init;
 89 var
 90     i:longint;
 91 begin
 92     read(n);
 93     for i:=1 to n do
 94       begin
 95         tree[i].root:=true;
 96         tree[i].size:=1;
 97         read(tree[i].fa);
 98         inc(tree[i].fa,i);
 99         if tree[i].fa>n then tree[i].fa:=n+1;
100       end;
101     tree[n+1].size:=1;
102     tree[n+1].root:=true;
103 end;
104 
105 procedure work;
106 var
107     i,x,y:longint;
108 begin
109     read(m);
110     for i:=1 to m do
111       begin
112         read(x,y);
113         inc(y);
114         if x=1 then
115           begin
116             access(y);
117             writeln(tree[tree[y].son[0]].size);
118           end
119         else
120           begin
121             read(x);
122             splay(y);
123             tree[tree[y].son[0]].fa:=tree[y].fa;
124             tree[tree[y].son[0]].root:=true;
125             tree[y].son[0]:=0;
126             tree[y].size:=tree[tree[y].son[1]].size+1;
127             tree[y].fa:=y+x;
128             if tree[y].fa>n then tree[y].fa:=n+1;
129           end;
130       end;
131 end;
132 
133 begin
134     init;
135     work;
136 end.

View Code