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
3
分块套路记于心：预处理整块！！！
预处理出每个点在块中跳的贡献(sum[i])，记录每个点跳出块外的地方(last[i])，这个倒着搞一遍for即可。。。
修改的话该点只会对块内的答案产生影响，所以只要在块内暴力根号n的修改
查询一路跳last直到出去，每次顶多根号跳根号n个块
综上总复杂度n*sqrt(n)
1.一开始TLE了，数组开小了
附上代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=;
int gi()
{
int x=;
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x;
}
int k[N],pos[N],l[N],r[N],n,m,block,cnt,last[N],sum[N];
void pre()
{
for(int i=;i<=cnt;i++) l[i]=(i-)*block+,r[i]=i*block;
r[cnt]=n;
for(int i=;i<=n;i++) pos[i]=(i-)/block+;
}
int query(int x)
{
int ret=;
while(x<=n) ret+=sum[x],x=last[x];
return ret;
}
void modify(int x,int K)
{
k[x]=K;
for(int i=x;i>=l[pos[x]];i--)
{
if(pos[i]==pos[i+k[i]]) last[i]=last[i+k[i]],sum[i]=sum[i+k[i]]+;
else last[i]=i+k[i],sum[i]=;
}
}
int main()
{
n=gi();
for(int i=;i<=n;i++) k[i]=gi();
block=(int) sqrt(n);
if(n%block==) cnt=n/block;
else cnt=n/block+;
pre();
for(int i=n;i>=;i--)
{
if(pos[i]==pos[i+k[i]]) last[i]=last[i+k[i]],sum[i]=sum[i+k[i]]+;
else last[i]=i+k[i],sum[i]=;
}
int type,x,K;m=gi();
for(int i=;i<=m;i++)
{
type=gi();
if(type==) x=gi(),x++,printf("%d\n",query(x));
else x=gi(),K=gi(),x++,modify(x,K);
}
}