题目描述

某天，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。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

输入输出样例

41 2 1 131 12 1 11 1

23

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=200020; 9 int read(){10     int x=0,f=1;char ch=getchar();11     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13     return x*f;14 }15 int block,cnt;16 int B[mxn],L[mxn],R[mxn];17 int nxt[mxn],k[mxn],w[mxn];18 int n,m;19 int clc(int st){20     int res=0;21     while(st<=n && st){22         res+=w[st];23         st=nxt[st];24     }25     return res;26 }27 int main(){28     n=read();29     int i,j;30     for(i=1;i<=n;i++)k[i]=read();31     block=sqrt(n);32     cnt=(n-1)/block+1;33     for(i=1;i<=cnt;i++){34         L[i]=R[i-1]+1;35         R[i]=i*block;36 //        printf("L:%d R:%d\n",L[i],R[i]);37     }38     R[cnt]=min(R[cnt],n);39     for(i=1;i<=n;i++)B[i]=(i-1)/block+1;40     for(i=n;i;i--){41         if(i+k[i]>n)w[i]=1;42         else if(B[i]==B[i+k[i]]){43                 w[i]=w[i+k[i]]+1;44                 nxt[i]=nxt[i+k[i]];45             }46             else{47                 w[i]=1;48                 nxt[i]=i+k[i];49             }50     }51     m=read();52     int op,x,y;53     while(m--){54         op=read();55         if(op==1){56             x=read()+1;57             printf("%d\n",clc(x));58         }59         else{60             x=read()+1;y=read();61             k[x]=y;62             for(i=x;i>=L[B[x]];i--){63                 if(B[i]==B[i+k[i]]){64                     w[i]=w[i+k[i]]+1;65                     nxt[i]=nxt[i+k[i]];66                 }67                 else{68                     w[i]=1;69                     nxt[i]=i+k[i];70                 }71             }72         }73     }74     return 0;75 }