Codeforces 13 E. Holes
問題
n個の穴があり、穴はそれぞれa[i]のエネルギーがを持つ。
i番目の穴にボールを入れると、i+a[i]番目の穴へボールが飛ぶ。
飛んだ先の穴からまた連鎖的に同じことがおこる。
- a[i]がnを超えると、その時点で連鎖は終了する。
このとき、次のm個のクエリに答えよ。
- 0 a b a番目の穴のエネルギーをbに変更する
- 1 a a番目の穴にボールを入れたときに、連鎖が終了するまでいくつの穴に入るかおよび、最後に入る穴はどれか出力する。
制約条件
n,m≦10^5
エネルギーは全て自然数
方針
平方分割。
「穴がどこへ行くか、その目的地までいくつの穴を通るか」
を、バケットの範囲内だけ圧縮しておく。
すると、エネルギーの変更のクエリは一回あたり、O(√n)
穴にボールを入れるクエリも一回あたりO(√n)でできることになり、
時間内に処理することができる。
ソースコード
const int SZ=400; int nxt[100000],jmp[100000]; int n,m; int a[100000]; void fix(int p){ int q=p+a[p]; if(q>=n)nxt[p]=-1, jmp[p]=1; else{ if(q/SZ!=p/SZ||nxt[q]<0)nxt[p]=q, jmp[p]=1; else nxt[p]=nxt[q], jmp[p]=jmp[q]+1; } } void run() { cin>>n>>m; rep(i,n)cin>>a[i]; for(int i=n-1;i>=0;i--)fix(i); rep(i,m){ int type,x,y; cin>>type>>x; if(type){ int p=-1,cnt=0; x--; while(x!=-1){ p=x; cnt+=jmp[x]; x=nxt[x]; } cout<<p+1<<" "<<cnt<<endl; } else{ cin>>y; x--; a[x]=y; for(int i=x;(i+SZ)/SZ==(x+SZ)/SZ;i--)fix(i); } } }