Description

某天，Lostmonkey發(fā)明了一種超級(jí)彈力裝置，為了在他的綿羊朋友面前顯擺，他邀請(qǐng)小綿羊一起玩?zhèn)€游戲。游戲一開(kāi)始，Lostmonkey在地上沿著一條直線擺上n個(gè)裝置，每個(gè)裝置設(shè)定初始彈力系數(shù)ki，當(dāng)綿羊達(dá)到第i個(gè)裝置時(shí)，它會(huì)往后彈ki步，達(dá)到第i+ki個(gè)裝置，若不存在第i+ki個(gè)裝置，則綿羊被彈飛。綿羊想知道當(dāng)它從第i個(gè)裝置起步時(shí)，被彈幾次后會(huì)被彈飛。為了使得游戲更有趣，Lostmonkey可以修改某個(gè)彈力裝置的彈力系數(shù)，任何時(shí)候彈力系數(shù)均為正整數(shù)。

Input

第一行包含一個(gè)整數(shù)n，表示地上有n個(gè)裝置，裝置的編號(hào)從0到n-1,接下來(lái)一行有n個(gè)正整數(shù)，依次為那n個(gè)裝置的初始彈力系數(shù)。第三行有一個(gè)正整數(shù)m，接下來(lái)m行每行至少有兩個(gè)數(shù)i、j，若i=1，你要輸出從j出發(fā)被彈幾次后被彈飛，若i=2則還會(huì)再輸入一個(gè)正整數(shù)k，表示第j個(gè)彈力裝置的系數(shù)被修改成k。對(duì)于20%的數(shù)據(jù)n,m<=10000，對(duì)于100%的數(shù)據(jù)n<=200000,m<=100000

Output

對(duì)于每個(gè)i=1的情況，你都要輸出一個(gè)需要的步數(shù)，占一行。

Sample Input

Sample Output

正解：LCT或分塊。

這題一眼看上去就是LCT，但是不會(huì)寫(xiě)。然后A過(guò)的人告訴我是分塊，想了一會(huì)兒yy出來(lái)了。。

記錄每個(gè)點(diǎn)跳到當(dāng)前塊的最后一個(gè)位置和跳到下一個(gè)塊第一個(gè)位置的距離，這個(gè)從n到1遞推就好。查詢時(shí)每次跳一個(gè)塊，所以最多跳sqrt(n)次。修改時(shí)只要修改當(dāng)前點(diǎn)和在這個(gè)塊中的前面的點(diǎn)，所以最多修改sqrt(n)次，那么總復(fù)雜度就是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;}