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了，数组开小了
附上代码
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 const int N=300050; 8 int gi() 9 { 10 int x=0; 11 char ch=getchar(); 12 while(ch<'0'||ch>'9') ch=getchar(); 13 while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); 14 return x; 15 } 16 int k[N],pos[N],l[N],r[N],n,m,block,cnt,last[N],sum[N]; 17 void pre() 18 { 19 for(int i=1;i<=cnt;i++) l[i]=(i-1)*block+1,r[i]=i*block; 20 r[cnt]=n; 21 for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1; 22 } 23 int query(int x) 24 { 25 int ret=0; 26 while(x<=n) ret+=sum[x],x=last[x]; 27 return ret; 28 } 29 void modify(int x,int K) 30 { 31 k[x]=K; 32 for(int i=x;i>=l[pos[x]];i--) 33 { 34 if(pos[i]==pos[i+k[i]]) last[i]=last[i+k[i]],sum[i]=sum[i+k[i]]+1; 35 else last[i]=i+k[i],sum[i]=1; 36 } 37 } 38 int main() 39 { 40 n=gi(); 41 for(int i=1;i<=n;i++) k[i]=gi(); 42 block=(int) sqrt(n); 43 if(n%block==0) cnt=n/block; 44 else cnt=n/block+1; 45 pre(); 46 for(int i=n;i>=1;i--) 47 { 48 if(pos[i]==pos[i+k[i]]) last[i]=last[i+k[i]],sum[i]=sum[i+k[i]]+1; 49 else last[i]=i+k[i],sum[i]=1; 50 } 51 int type,x,K;m=gi(); 52 for(int i=1;i<=m;i++) 53 { 54 type=gi(); 55 if(type==1) x=gi(),x++,printf("%d ",query(x)); 56 else x=gi(),K=gi(),x++,modify(x,K); 57 } 58 }