记录编号	551020	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	2.149 s
提交时间	2020-04-03 00:50:24	内存使用	19.00 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200101;
int st[N];
struct PE
{
	int ch[2],size,fa,lazy;
	PE()
	{
		ch[0]=0;
		ch[1]=0;
		size=0;
		fa=0;
		lazy=0;
	}
};
PE t[N];
int ls(int x)
{
	return t[x].ch[0];
}
int rs(int x)
{
	return t[x].ch[1];
}
bool nroot(int x)
{
	return ls(t[x].fa)==x||rs(t[x].fa)==x;
}
void pushup(int x)
{
	t[x].size=t[ls(x)].size+t[rs(x)].size+1;
}
void round(int x)
{
	int S=t[x].ch[0];
	t[x].ch[0]=t[x].ch[1];
	t[x].ch[1]=S;
	t[x].lazy^=1;
}
void pushdown(int x)
{
	if(t[x].lazy)
	{
		if(ls(x))
		round(ls(x));
		if(rs(x))
		round(rs(x));
		t[x].lazy=0;
	}
}
void rotate(int x)
{
	int y=t[x].fa;
	int z=t[y].fa;
	int k=(t[y].ch[1]==x);
	int w=t[x].ch[k^1];
	if(nroot(y))
	{
		t[z].ch[t[z].ch[1]==y]=x;
	}
	t[y].ch[k]=w;
	if(w)
		t[w].fa=y;
	t[x].ch[k^1]=y;
	t[y].fa=x;
	t[x].fa=z;
	pushup(y);
	pushup(x);
}
void Splay(int x)
{
	int y=x,z=0;
	st[++z]=y;
	while(nroot(y))
	{
		y=t[y].fa;
		st[++z]=y;
	}
	while(z)
	{
		pushdown(st[z--]);
	}
	while(nroot(x))
	{
		y=t[x].fa;
		z=t[y].fa;
		if(nroot(y))
		{
			(t[y].ch[1]==x)^(t[z].ch[1]==y)?rotate(x):rotate(y);
		}
		rotate(x);
	}
	pushup(x);
}
void Access(int x)
{
	for(int y=0;x;y=x,x=t[x].fa)
	{
		Splay(x);
		t[x].ch[1]=y;
		pushup(x); 
	}
}
void Makeroot(int x)
{
	Access(x);
	Splay(x);
	round(x);
}
void Split(int x,int y)
{
	Makeroot(x);
	Access(y);
	Splay(y);
}
int Findroot(int x)
{
	Access(x);
	Splay(x);
	while(t[x].ch[0])
	{
		pushdown(x);
		x=t[x].ch[0];
	}
	Splay(x);
	return x; 
}
void Link(int x,int y)
{
	Makeroot(x);
	if(Findroot(y)!=x)
	{
		t[x].fa=y;
	}
}
void Cut(int x,int y)
{
	Makeroot(x);
	if(Findroot(y)==x&&t[y].fa==x&&t[y].ch[0]==0)
	{
		t[x].ch[1]=0;
		t[y].fa=0;
		pushup(x);
	}
}
int n,m,a1,a2,a3,a4;
int Val[N];
int main()
{
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n+1;i++)
	{
		t[i].size=1;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&Val[i]);
		Link(i,min(i+Val[i],n+1));
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a1,&a2);
		if(a1==1)
		{
			a2++;
			Split(a2,n+1);
			printf("%d\n",t[n+1].size-1); 
		}
		else
		{
			scanf("%d",&a3);
			a2++;
			Cut(a2,min(a2+Val[a2],n+1));
			Val[a2]=a3;
			Link(a2,min(a2+a3,n+1));
		}
	}
	return 0;
}