Codeforces 13 E. Holes

問題

n個の穴があり、穴はそれぞれa[i]のエネルギーがを持つ。


i番目の穴にボールを入れると、i+a[i]番目の穴へボールが飛ぶ。
飛んだ先の穴からまた連鎖的に同じことがおこる。

  1. 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);
		}
	}
}