某天，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的情况，你都要输出一个需要的步数，占一行。
思路：分块，cnt表示从当前块跳出去需要几步，_next表示从当前块跳出去后所在的位置
代码：
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<list> #include<numeric> using namespace std; #define PI acos(-1.0) #define LL long long #define ULL unsigned long long #define INF 0x3f3f3f3f #define mm(a,b) memset(a,b,sizeof(a)) #define PP puts("*********************"); template<class T> T f_abs(T a){ return a > 0 ? a : -a; } template<class T> T gcd(T a, T b){ return b ? gcd(b, a%b) : a; } template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;} // 0x3f3f3f3f3f3f3f3f // 0x3f3f3f3f const int maxn=2e5+50; int arr[maxn];//下标从0开始 int cnt[maxn],_next[maxn]; int siz,tot;//块的大小，数目，第一块为0~siz-1 int n; void maintain(int pos){ int lb=pos/siz*siz,rb=min(n,lb+siz)-1; for(int i=pos;i>=lb;i--){ if(i+arr[i]>rb){ cnt[i]=1; _next[i]=i+arr[i]; } else{ cnt[i]=cnt[i+arr[i]]+1; _next[i]=_next[i+arr[i]]; } } } void init(){//初始化块状数组 siz=(int)sqrt(n*1.0); tot=n/siz; if(n%siz!=0) tot++; for(int i=1;i<=tot;i++) maintain(min(i*siz,n)-1); } void update(int pos,int val){ arr[pos]=val; maintain(pos); } int query(int L){ int pos1=L/siz,pos2=(n-1)/siz,now=L; int res=0; for(int i=pos1;i<=pos2;){ res+=cnt[now]; now=_next[now]; i=max(now/siz,i+1); } return res; } int main(){ int m,op,x,y; while(~scanf("%d",&n)){ for(int i=0;i<n;i++) scanf("%d",&arr[i]); init(); scanf("%d",&m); while(m--){ scanf("%d",&op); if(op==1){ scanf("%d",&x); int ans=query(x); printf("%d\n",ans); } else{ scanf("%d%d",&x,&y); update(x,y); } } } return 0; }