记录编号	417429	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	HZOI_蒟蒻一只	是否通过	通过
代码语言	C++	运行时间	1.571 s
提交时间	2017-06-25 16:45:34	内存使用	3.03 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cctype>
using namespace std;
const int maxn=200005;
int n,m,cnt;
const int block=450;
int pt[maxn],st[maxn],k[maxn],belong[maxn];
inline int cal(int x)
{
	int tmp=0;
	while(x)
	{
		tmp+=st[x];
		x=pt[x];
	}
	return tmp;
}
void pre()
{
	int tot=1,temp=0;
	for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;
}
int haha()
{
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&k[i]);
	pre();
	for(int i=n;i;i--)
	{
		if(i+k[i]>n)
		{
			st[i]=1;
			pt[i]=0;
		}
		else if(belong[i]==belong[i+k[i]])
			{
				st[i]=st[i+k[i]]+1;
				pt[i]=pt[i+k[i]];
			}
		else
		{
			st[i]=1;
			pt[i]=i+k[i];
		}
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);y++;
		if(x==1)printf("%d\n",cal(y));
		else
		{
			scanf("%d",&k[y]);
			for(int i=y;i>=0&&belong[i]==belong[y];i--)
			{
				if(i+k[i]>n)
				{
					st[i]=1;
					pt[i]=0;
				}
				else if(belong[i]==belong[i+k[i]])
				{
					st[i]=st[i+k[i]]+1;
					pt[i]=pt[i+k[i]];
				}
				else
				{
					st[i]=1;
					pt[i]=i+k[i];
				}
			}
		}
	}
}
int sb=haha();
int main(){;}