弹飞绵羊

题目的网址为：

http://www.lydsy.com/JudgeOnline/problem.php?id=2002

题目大意

有N个点，每个点有一个系数a[i]，你处于位置i可以走到i+a[i]，若i+a[i]>n则你走出了地图。 现M个操作有两种： 1、把a[j]修改为k。 2、询问你位于点j时，需要走多少部走出地图。

数据范围

1<=n<=200000, 1<=m<=100000。

题解

这是一道经典的LCT(动态树)例题，然而，我这个蒟蒻，并不会用动态树，我只会分块这种相对低级的方法。

将原序列分成 n√ 块， ei 表示当前 i 跳出i所在的那一块需要的步数， eni 表示跳出块后的位置。

执行询问操作时，只需要不断地跳出下一个块，跳到不能再跳为止，最多跳 n√ 次。具体实现如下：

ans:=0; while op<=n do begin ans:=ans+e[op]; op:=en[op]; end;

执行修改操作时，只需修改本块中在该数之前的 ei 和 eni ，从前往后修改，最多修改 n√ 次。具体实现如下：

for o:=op downto l do //l为op所在块中的左边界 begin if o+k[o]>r then //r为op所在块中的右边界 begin en[o]:=u; e[o]:=1; end else begin en[o]:=en[u]; e[o]:=e[u]+1; end; end;

初始化的方法跟在执行修改操作时的更新方法差不多，就不多讲了。 总时间复杂度 O (m n√ )，分块算法，奥妙重重！

Code(Pascal)

var k,en,ne:array[0..300000] of longint; ku,l,r,i,j,m,n,o,p,u,op,ans:longint; function min(a,b:Longint):longint; begin if a<b then exit(a) else exit(b); end; begin readln(n); for i:=1 to n do read(k[i]); ku:=trunc(sqrt(n)); p:=n div ku; if n mod p<>0 then inc(ku); for i:=1 to ku do begin l:=(i-1)*p+1; r:=min(i*p,n); for o:=r downto l do begin u:=o+k[o]; if u>r then begin en[o]:=u; ne[o]:=1; end else begin en[o]:=en[u]; ne[o]:=ne[u]+1; end; end; end; readln(m); for i:=1 to m do begin read(op); if op=1 then begin readln(op); inc(op); ans:=0; while op<=n do begin ans:=ans+ne[op]; op:=en[op]; end; writeln(ans); end else begin readln(op,u); inc(op); k[op]:=u; l:=(op div p)*p+1; r:=l+p-1; if op mod p=0 then begin l:=l-p; r:=r-p; end; for o:=op downto l do begin u:=o+k[o]; if u>r then begin en[o]:=u; ne[o]:=1; end else begin en[o]:=en[u]; ne[o]:=ne[u]+1; end; end; end; end; end.