mdzz刚写了一次不知道怎么不见了。。醉了。 算了重新写一次吧，lct出门左转不送~~ 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 提议还是很好理解的吗，很容易想到用分块的方法，其实说实话，只要你会分块，基本上也就等于会了块状链表。。 具体看我代码注释：
var i,j,p,n,m,x,y:longint; f,go,bl,k:array[0..200000]of longint;//f:跳去的点编号，go:跳去的块编号，bl[i]表示第i个点所在的块 //k:跳到下一块所需的步数 procedure init; var i,j,tot,p,sq,p1:longint; begin readln(n); sq:=trunc(sqrt(n)); p:=sq; tot:=0; for i:=1 to n do begin //预处理分块 if p=sq then begin p:=1; inc(tot); bl[i]:=tot; end else begin bl[i]:=tot; inc(p); end; read(f[i]); f[i]:=f[i]+i;//直接加上便于处理 end; //对于有跳跃关系的每两个点进行处理。 for i:=n downto 1 do begin p:=f[i]; if (bl[i]<>bl[p])or(p>n)then//如果跳出本块或跳出界 begin go[i]:=p; k[i]:=1; end else begin//如果在本块内直接继承后一个点的信息 go[i]:=go[p]; k[i]:=k[p]+1; end; end; end; function ask(x:longint):longint;//统计答案比较白痴就不用说了。 var i,j,ans:longint; begin ans:=0; while x<=n do begin inc(ans,k[x]); x:=go[x]; end; exit(ans); end; procedure change(x,y:longint); var i,j,p,tot:longint; begin j:=bl[x]; f[x]:=y; p:=y; //先对点进行预处理时的关系改变 if (bl[p]<>bl[x])or(p>n)then begin go[x]:=p; k[x]:=1; end else begin go[x]:=go[p]; k[x]:=k[p]+1; end; //暴力重构当前块处理方法和上面一样 for i:=x downto 1 do begin p:=f[i]; if bl[i]<>bl[x] then break;//因为是倒着处理，只要不在本块内后面的都不在本块内，自己手玩一下就知道。 if bl[p]=bl[i] then begin go[i]:=go[p]; k[i]:=k[p]+1; end else begin go[i]:=p; k[i]:=1; end; end; end; begin init; readln(m); for i:=1 to m do begin read(p); if p=1 then begin readln(x); inc(x);//题目中说了编号是0到n-1 writeln(ask(x)); end else begin readln(x,y); inc(x); y:=y+x; change(x,y); end; end; end.