bzoj 2002 Bounce 弹飞绵羊

bzoj 2002 Bounce 弹飞绵羊

• 设一个虚拟节点表示被弹飞,则每个点的后继点是唯一确定的,每个点向它的后继点连边,就形成了一颗树.
• 询问就是问某个节点到虚拟节点的路径长度,修改就删除原来向后继点的边,向新后继点连边.
• 用一颗 (LCT) 来维护即可.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int read()
{
	int x=0;
	bool pos=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())
		if(ch=='-')
			pos=0;
	for(;isdigit(ch);ch=getchar())
		x=x*10+ch-'0';
	return pos?x:-x;
}
int n,m,Rt;
const int MAXN=2e5+10;
namespace LCT{
	int stk[MAXN],tp;
	struct node{
		int ch[2];
		int fa;
		int rev;
		int siz;
		node()
			{
				rev=0;
				siz=1;
				ch[0]=ch[1]=fa=0;
			}
	}tree[MAXN];
	#define root tree[x]
	#define lson tree[root.ch[0]]
	#define rson tree[root.ch[1]]
	void pushup(int x)
		{
			if(!x)
				return;
			root.siz=lson.siz+1+rson.siz;
		}
	void inverse(int x)
		{
			swap(root.ch[0],root.ch[1]);
			root.rev^=1;
		}
	void pushdown(int x)
		{
			if(root.rev)
				{
					if(root.ch[0])
						inverse(root.ch[0]);
					if(root.ch[1])
						inverse(root.ch[1]);
					root.rev=0;
				}
		}
	bool isroot(int x)
		{
			return tree[root.fa].ch[0]!=x && tree[root.fa].ch[1]!=x;
		}
	void rotate(int x)
		{
			int y=tree[x].fa,z=tree[y].fa;
			int k=tree[y].ch[1]==x;
			if(!isroot(y))
				tree[z].ch[tree[z].ch[1]==y]=x;
			tree[x].fa=z;
			tree[y].ch[k]=tree[x].ch[k^1];
			tree[tree[x].ch[k^1]].fa=y;
			tree[x].ch[k^1]=y;
			tree[y].fa=x;
			pushup(y);
			pushup(x);
			pushup(z);
		}
	void splay(int x)
		{
			tp=0;
			stk[++tp]=x;
			for(int pos=x;!isroot(pos);pos=tree[pos].fa)
				stk[++tp]=tree[pos].fa;
			while(tp)
				pushdown(stk[tp--]);
			while(!isroot(x))
				{
					int y=tree[x].fa,z=tree[y].fa;
					if(!isroot(y))
						(tree[y].ch[0]==x)^(tree[z].ch[0]==y)?rotate(x):rotate(y);
					rotate(x);	
				}
			pushup(x);
		}
	void Access(int x)
		{
			for(int y=0;x;y=x,x=tree[x].fa)
				{
					splay(x);
					tree[x].ch[1]=y;
					pushup(x);
				}
		}
	void makeroot(int x)
		{
			Access(x);
			splay(x);
			inverse(x);
		}
	int findroot(int x)
		{
			Access(x);
			splay(x);
			while(tree[x].ch[0])
				x=tree[x].ch[0];
			return x;
		}
	void split(int x,int y)
		{
			makeroot(x);
			Access(y);
			splay(y);
		}
	void Link(int x,int y)
		{
			makeroot(x);
			tree[x].fa=y;	
		}
	void Cut(int x,int y)
		{
			split(x,y);
			tree[y].ch[0]=0;
			tree[x].fa=0;
			pushup(y);
		}
};
using namespace LCT;
int K[MAXN];
int main()
{
	tree[0].siz=0;
	n=read();
	Rt=n+1;
	for(int i=1;i<=n;++i)
		{
			int k=read();
			K[i]=k;
			if(k+i<=n)
				tree[i].fa=k+i;
			else
				tree[i].fa=Rt;
		}
	m=read();
	while(m--)
		{
			int op=read();
			if(op==1)
				{
					int x=read();
					++x;
					split(x,Rt);
					printf("%d
",tree[tree[Rt].ch[0]].siz);
				}
			else
				{
					int x=read();
					++x;
					int y=x+K[x]>n?Rt:x+K[x];
					Cut(x,y);
					K[x]=read();
					y=x+K[x]>n?Rt:x+K[x];
					Link(x,y);
				}
		}
	return 0;
}