题目描述
某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
输入输出格式
输入格式：
第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1。
接下来一行有n个正整数，依次为那n个装置的初始弹力系数。
第三行有一个正整数m，
接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。
输出格式：
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
输入输出样例
4
1 2 1 1
3
1 1
2 1 1
1 1
2
3
说明
对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000
解题思路
LCT不会，或者分块。
分成$\sqrt{n}$块，对于每个格子，维护三个值——$a[i]$第$i$个点的弹力系数，即弹射距离；$nxtn[i]$，弹射到下一个块所需的步数；$nxtp[i]$，从第i个点开始跳，直到离开这个块时的下一个位置(便于统计是一个块一个块地跳)。
输入数据后，从后向前递推求出$nxtp[i]$和$nxtn[i]$。
询问从$x$点开始，要弹飞所需的步数，就从$x$开始，利用$nxtp[i]$暴力跳块，用$nxtn[i]$暴力统计答案，直到飞了，输出答案。
修改第$x$个点的弹力系数，就先把$a[x]$的值修改了，然后从后往前暴力递推$x$所在块的$nxtp[i]$和$nxtn[i]$。
源代码
#include<stdio.h>
#include<math.h> int n,t,m;
int a[]/*弹力*/,nxtp[]/*到下一块的位置*/,nxtn[]/*到下一块的步数*/; int main()
{
//freopen("test.in","r",stdin);
scanf("%d",&n);
t=sqrt(n);//块数
for(int i=;i<n;i++)
{
scanf("%d",a+i);
}
for(int i=n-;i>=;i--)//i/t获得块数
{
if(i+a[i]>=n) nxtp[i]=n,nxtn[i]=;
else if(i/t!=(i+a[i])/t) nxtp[i]=i+a[i],nxtn[i]=;
else nxtp[i]=nxtp[i+a[i]],nxtn[i]=+nxtn[i+a[i]];
}
scanf("%d",&m);
while(m--)
{
int opt;
scanf("%d",&opt);
if(opt==)
{
int x;
scanf("%d",&x);
int ans=;
while(x<n)
{
ans+=nxtn[x];
x=nxtp[x];
}
printf("%d\n",ans);
}
else
{
int x,y;
scanf("%d%d",&x,&y);
a[x]=y;
for(int i=(x/t+)*t;i>=x/t*t;i--)
{
if (i + a[i] >= n)
nxtp[i] = n, nxtn[i] = ;
else if (i / t != (i + a[i]) / t)
nxtp[i] = i + a[i], nxtn[i] = ;
else
nxtp[i] = nxtp[i + a[i]], nxtn[i] = + nxtn[i + a[i]];
}
}
}
return ;
}