记录编号	599290	评测结果	ATTTTTTTTT
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	10
用户昵称	徐诗畅	是否通过	未通过
代码语言	C++	运行时间	17.996 s
提交时间	2025-03-07 16:23:52	内存使用	6.40 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,a[N],len;

int b[505][505],c[505][505],d[505][505];
int main(){
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
	len=sqrt(n);
	for(int i = 1;i<=ceil(n*1.0/len);i++){
		int en;
		if(i==ceil(n*1.0/len)) en=(n-n/len*len)==0?len:(n-n/len*len);
		else en=len; 
		for(int j=1;j<=en;j++){ 
			int pos=j;
			while(pos<=en){
				pos+=a[len*(i-1)+pos]; b[i][j]++;
			}
			pos+=(i-1)*len;
			if(pos%len==0) c[i][j]=pos/len,d[i][j]=len;
			else c[i][j]=pos/len+1,d[i][j]=pos-len*(c[i][j]-1);
		}
	}
	scanf("%d",&m);
	for(int i = 1;i<=m;i++){
		int op,x,y; cin>>op; //cout<<op<<" "<<x<<" "<<y<<endl;
		if(op==1){
			scanf("%d",&x); x++; //cout<<op<<" "<<x<<endl;
			if(x>n) {puts("0"); continue;}
			int bn,pos,ans=0;
			if(x%len==0) bn=x/len,pos=len;
			else{bn=x/len+1; pos=x-len*(bn-1);} 
			while((bn-1)*len+pos<=n){ //cout<<bn<<" "<<pos<<endl;
				int bn1=bn,pos1=pos;
				ans+=b[bn][pos];
				bn=c[bn1][pos1];
				pos=d[bn1][pos1];
			}
			printf("%d\n",ans);
		}
		else{
			scanf("%d%d",&x,&y); x++; //cout<<op<<" "<<x<<" "<<endl;
			if(x>n) continue;
			a[x]=y; 
			int bn,en;
			if(x%len==0) bn=x/len;
			else bn=x/len+1;
			if(bn==ceil(n*1.0/len)) en=(n-n/len*len)==0?len:(n-n/len*len);
	     	else en=len;
		    for(int j=1;j<=en;j++){ //cout<<c[447][192]<<" "<<d[447][192]<<endl; 
		    	int pos=j; b[bn][j]=0;
		    	while(pos<=en){
			    	pos+=a[len*(bn-1)+pos]; b[bn][j]++;
		    	}
		    	pos+=(bn-1)*len;
		    	if(pos%len==0) c[bn][j]=pos/len,d[bn][j]=len;
		    	else c[bn][j]=pos/len+1,d[bn][j]=pos-len*(c[bn][j]-1);
		    	//cout<<d[bn][j]<<endl;
	    	}
		}
	}
	return 0;
}