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。
Output
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
Sample Input
4
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3
Solution
比较简单的分块
对每个分块维护两个值：跳出这个块需要的次数、跳出这个块后所在位置
那么查询和修改就很简单了~
Code
//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define R(i,a,b) for(register int i=(b);i>=(a);i--)
using namespace std;
int rd() {
int x=0,f=1; char c=getchar();
while(!isdigit(c)) {if(c=='-')f=-f; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*f;
}
const int N=200010;
int n,q,blo;
int da[N],cnt[N],to[N],bl[N],l[N],r[N];
void init() {
R(i,1,n) {
if(bl[i]!=bl[i+1]) r[bl[i]]=i;
if(bl[i]!=bl[i-1]) l[bl[i]]=i;
if(i+da[i]>n) cnt[i]=1,to[i]=n+1;
else if(i+da[i]>r[bl[i]]) cnt[i]=1,to[i]=i+da[i];
else cnt[i]=cnt[i+da[i]]+1,to[i]=to[i+da[i]];
}
}
void query(int x) {
int ans=0;
while(x!=n+1) ans+=cnt[x],x=to[x];
printf("%d\n",ans);
return ;
}
void change() {
int x=rd()+1,k=rd();
da[x]=k;
R(i,l[bl[x]],x) //1
if(i+da[i]>n) cnt[i]=1,to[i]=n+1;
else if(i+da[i]>r[bl[i]]) cnt[i]=1,to[i]=i+da[i];
else cnt[i]=cnt[i+da[i]]+1,to[i]=to[i+da[i]];
}
int main() {
n=rd(); blo=sqrt(n);
F(i,1,n) da[i]=rd(),bl[i]=(i-1)/blo+1;
init();
q=rd();
while(q--) {
int opt=rd();
if(opt==1) query(rd()+1);
else change();
}
return 0;
}