记录编号	155535	评测结果	AAAAAAAAAA
题目名称	1689.[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	Rivendell	是否通过	通过
代码语言	C++	运行时间	1.787 s
提交时间	2015-03-29 16:29:38	内存使用	3.56 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[200001]={0},ku[500][2]={0},kuai[500][500]={0},f[200001][2]={0};
int main()
{
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout);
	
	int i,j,k,n,m,len,block,ans;
	scanf("%d",&n);
	len=floor(sqrt(n));
	if (n%len==0) block=n/len;
	else block=n/len+1;
	for (i=1;i<=block;++i)
	{
		ku[i][0]=len*(i-1)+1;
		ku[i][1]=min(n,len*i);
	}
	for (i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<=block;++i)
	  for (j=ku[i][1];j>=ku[i][0];--j)
	  {
	  	  if (j+a[j]>ku[i][1])
	  	  {
	  	  	f[j][0]=1;f[j][1]=j+a[j];
	  	  }
	  	  else
	  	  {
	  	  	f[j][0]=f[j+a[j]][0]+1;f[j][1]=f[j+a[j]][1];
	  	  }
	  }
	scanf("%d",&m);++m;
	while(--m)
	{
		scanf("%d%d",&i,&j);
		++j;
		if (i==1)
		{
			ans=0;
			for (;j<=n;j=f[j][1]) ans+=f[j][0];
			printf("%d\n",ans);
		}
		else
		{
			scanf("%d",&k);
			i=(j-1)/len+1;a[j]=k;
			for (;j>=ku[i][0];--j)
			{
				if (j+a[j]>ku[i][1])
				{
					f[j][0]=1;f[j][1]=j+a[j];
				}
				else
				{
					f[j][0]=f[j+a[j]][0]+1;f[j][1]=f[j+a[j]][1];
				}
			}
		}
	}
	
	fclose(stdin);
	fclose(stdout);
}