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

Sample Output

正解：LCT或分塊。

這題一眼看上去就是LCT，但是不會寫。然后A過的人告訴我是分塊，想了一會兒yy出來了。。

記錄每個點跳到當前塊的最后一個位置和跳到下一個塊第一個位置的距離，這個從n到1遞推就好。查詢時每次跳一個塊，所以最多跳sqrt(n)次。修改時只要修改當前點和在這個塊中的前面的點，所以最多修改sqrt(n)次，那么總復雜度就是m*sqrt(n)。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define inf (1<<30)#define il inline#define RG register#define ll long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;int k[400010],bl[400010],far[400010],dis[400010],n,m,block;il int gi(){    RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}il void work(){    n=gi(),block=sqrt(n); for (RG int i=1;i<=n;++i) k[i]=gi(),bl[i]=(i-1)/block+1; m=gi();    for (RG int i=n+1;i<=2*n;++i) bl[i]=i;    for (RG int i=n;i;--i)	if (bl[i+k[i]]>bl[i]) far[i]=i,dis[i]=1;	else far[i]=far[i+k[i]],dis[i]=dis[i+k[i]]+1;    for (RG int i=1;i<=m;++i){	RG int type=gi(),x=gi()+1,ans=0;	if (type==1){ while (x<=n) ans+=dis[x],x=far[x]+k[far[x]]; PRintf("%d/n",ans); }	if (type==2){	    RG int K=gi(),Bl=bl[x]; k[x]=K;	    for (;bl[x]==Bl;--x)		if (bl[x+k[x]]>bl[x]) far[x]=x,dis[x]=1;		else far[x]=far[x+k[x]],dis[x]=dis[x+k[x]]+1;	}    }    return;}int main(){    File("bounce");    work();    return 0;}