我其实是在codevs上看到它的题号后才去做这道题的。。。2333。。。

　　题目传送门：codevs:/　　bzoj:

　　题意已经说的很清晰了，蓝鹅……我不会做。

　　看题解有两种写法：分块和link-cut tree。但是lct我不会，只能用分块了。

　　但是怎么分块呢？

　　我们想一下有什么暴力写法。一种是记录每个反弹装置能往后弹多长距离，这样效率是修改O(1)+查询O(n)。另一种是记录从每个反弹装置开始到被弹飞要被弹多少次，这样效率是修改O(n)+查询O(1)。我们可以想一个介于两者之间的做法，比如……把序列平均分成m块，记录每个反弹装置弹到下一个块要弹多少次 和 会弹到下一个块的哪一个装置。这样一来，效率就变成了修改O(n/m)+查询O(m)，总时间复杂度就是O(n*(n/m+m))。显然，如果要使效率最快m就取√n。

　　接下来就可以打代码+AC了。（代码真心很短）

代码：

var a,ne,x,y:array[0..200010]of longint;  n,m,i,j,k,p,t,q,ans:longint;begin  read(n); p:=trunc(sqrt(n));  for i:=0 to n-1 do begin    read(a[i]); ne[i]:=(i div p+1)*p;  end;  for i:=0 to n-1 do begin    x[i]:=i; y[i]:=0;    while(x[i]
      
       
        =ne[j] then begin          x[j]:=j+a[j]; y[j]:=1;        end        else begin          x[j]:=x[j+a[j]]; y[j]:=y[j+a[j]]+1;        end;    end;  end;end.
       
      

 　　lct等学了再补吧。。。