bzoj 2002 Bounce 弹飞绵羊

时间：2021-08-27 15:30:54

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\n",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;

}

相关文章