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
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3
动态树模板问题
link/cut tree来解决
其实也可以分块来搞……跟ioi的大象很像
每个点向他弹射到的点连边，弹飞的连向0，这样全图就形成了一棵树
询问的话，就是查询改点到根节点上有多少个节点
修改的话，就是更改一个点的祖先
{$inline on}
program bzoj2002;
var
n,m,i,j,k,o:longint;
fa,father,left,right,total:array [0..200001] of longint;
function sum (now:longint):longint;inline;
var
ans:longint;
begin
if now=0 then exit(0);
ans:=0;
repeat
ans:=ans+total[now]+1;
now:=right[now];
until now=0;
exit(ans);
end;
procedure rotate (son,fat:longint);
begin
if father[fat]<>0 then
begin
if left[father[fat]]=fat then
left[father[fat]]:=son
else
right[father[fat]]:=son;
end;
father[son]:=father[fat];
father[fat]:=son;
if left[fat]=son then
begin
if right[son]<>0 then father[right[son]]:=fat;
left[fat]:=right[son];
right[son]:=fat;
total[fat]:=total[fat]-total[son]-1;
end
else
begin
if left[son]<>0 then father[left[son]]:=fat;
right[fat]:=left[son];
left[son]:=fat;
total[son]:=total[son]+total[fat]+1;
end;
end;
procedure access (now:longint);
var
i,k,o:longint;
begin
while fa[now]<>0 do
begin
while father[now]<>0 do rotate(now,father[now]);
i:=now;
while right[i]<>0 do i:=right[i];
k:=fa[i];
if k=0 then break;
while father[i]<>0 do rotate(i,father[i]);
while father[k]<>0 do rotate(k,father[k]);
o:=0;
if left[k]<>0 then
begin
o:=o-sum(left[k]);
father[left[k]]:=0;
end;
o:=o+sum(i);
left[k]:=i;
father[i]:=k;
total[k]:=total[k]+o;
now:=k;
end;
end;
begin
read(n);
for i:=1 to n do
begin
read(fa[i]);
fa[i]:=fa[i]+i;
if fa[i]>n then fa[i]:=0;
end;
read(m);
for j:=1 to m do
begin
read(o);
if o=1 then
begin
read(i);
inc(i);
access(i);
while father[i]<>0 do rotate(i,father[i]);
i:=right[i];
writeln(sum(i)+1);
end
else
begin
read(i,k);
inc(i);
o:=i+k;
if o>n then o:=0;
if fa[i]=o then continue;
while father[i]<>0 do rotate(i,father[i]);
if right[i]<>0 then father[right[i]]:=0;
right[i]:=0;
fa[i]:=o;
access(i);
end;
end;
end.