题解【[HNOI2010]弹飞绵羊】

\[\texttt{Description}
\]

有 \(n\) 个弹力装置排成一排，第 \(i\) 个弹力装置的弹力系数是 \(k_i\) ，绵羊到第 \(i\) 个装置时，会被弹到第 \(i+k_i\) 个弹力装置，若第 \(i+k_i\) 个装置不存在，则绵羊被弹飞。

你要维护这 \(n\) 个弹力装置，支持 \(2\) 种操作：

1 x 询问绵羊初始在第 \(x\) 个弹力装置时，被弹几次后被弹飞。
2 x y 将 \(k_x\) 改成 \(y\) 。

\[\texttt{Solution}
\]

我们把弹力装置抽象成一个点，弹力装置的这种位移操作抽象成一条边，即有 \(n\) 个点，第 \(i\) 个点向第 \(i+k_i\) 个点连一条边，考虑到绵羊被弹飞的情况，我们新建一个虚拟节点 \(n+1\) ，若绵羊被第 \(i\) 个弹力装置弹飞（即 \(i+k_i>n\)），我们就使第 \(i\) 个点向第 \(n+1\) 点连一条边。
考虑到每个节点都向后连边，我们建出来的图定是一个森林。
对于查询操作，就是问第 \(x\) 个节点与第 \(n+1\) 个节点之间有几条边。
对于修改操作，就是删去 \(x\) 原来向后连的边，再使得 \(x\) 向后新连一条边。
发现需要动态维护森林，于是我们就可以用动态维护森林的利器：\(\mathsf{LCT}\) 。
对于查询操作，我们依次调用 Make_root(x)，access(n + 1)，splay(n + 1)，就把 \(x\) 到 \(n+1\) 的路径分出来了，若在辅助树上维护个 \(size_i\)（子树大小），此时答案即为 \(size_{n+1}-1\) （边数 \(=\) 点数 \(-\) \(1\)）。
对于修改操作，我们调用 Cut(x, x + k[x] > n ? n + 1 : x + k[x]) ，表示把 \(x\) 原来连出去的边删掉，再调用 k[x] = y 修改 \(k_x\) 的值，再调用 Link(x, x + k[x] > n ? n + 1 : x + k[x])，表示将 \(x\) 新连出去一条边。

\[\texttt{Code}
\]

#include<cstdio>

#include<algorithm>

#define RI register int

using namespace std;

inline int read()

{

	int x=0,f=1;char s=getchar();

	while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}

	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

	return x*f;

}

const int N=1001000;

int n,m;

int fa[N],ch[N][2],k[N],size[N]; bool rev[N];

int len,que[N];

#define lc(x) ch[x][0]

#define rc(x) ch[x][1]

void upd(int x)

{

	size[x]=size[lc(x)]+size[rc(x)]+1;

}

void spread(int x)

{

	if(rev[x]==true)

	{

		std::swap(lc(x),rc(x));

		rev[lc(x)]^=1;rev[rc(x)]^=1;

		rev[x]=false;

	}

}

int get(int x)

{

	return rc(fa[x])==x;

}

int Is_root(int x)

{

	return lc(fa[x])!=x&&rc(fa[x])!=x;

}

void rotate(int x)

{

	int y=fa[x],z=fa[y],chk=get(x);

	if(!Is_root(y))ch[z][ch[z][1]==y]=x;

	ch[y][chk]=ch[x][chk^1];fa[ch[x][chk^1]]=y;

	ch[x][chk^1]=y,fa[y]=x,fa[x]=z;

	upd(y),upd(x);

}

void splay(int x)

{

	que[len=1]=x;

	for(RI p=x;!Is_root(p);p=fa[p])que[++len]=fa[p];

	for(RI i=len;i>=1;i--)spread(que[i]);

	for(;!Is_root(x);rotate(x))

		if(!Is_root(fa[x]))rotate(get(x)==get(fa[x])?fa[x]:x);

}

void access(int x)

{

	for(RI y=0;x;y=x,x=fa[x])

	{

		splay(x);

		rc(x)=y,fa[y]=x;

		upd(x);

	}

}

int Find_root(int x)

{

	access(x);

	splay(x);

	while(spread(x),lc(x))

		x=lc(x);

	splay(x);

	return x;

}

void Make_root(int x)

{

	access(x);

	splay(x);

	rev[x]^=1;

}

void Link(int x,int y)

{

	if(Find_root(x)==Find_root(y))

		return;

	Make_root(x);

	fa[x]=y;

}

void Cut(int x,int y)

{

	Make_root(x);

	access(y);

	splay(y);

	if(lc(y)!=x||lc(x)||rc(x))

		return;

	lc(y)=fa[x]=0;

	upd(y);

}

int ask(int x,int y)

{

	Make_root(x);

	access(y);

	splay(y);

	return size[y];

}

int main()

{

	n=read();

	for(RI i=1;i<=n;i++)

		k[i]=read();

	for(RI i=1;i<=n;i++)

		Link(i,i+k[i]>n?n+1:i+k[i]);

	m=read();

	while(m--)

	{

		int opt=read(),x=read()+1;

		switch(opt)

		{

			case 1:{

				printf("%d\n",ask(x,n+1)-1);

				break;

			}

			case 2:{

				Cut(x,x+k[x]>n?n+1:x+k[x]);

				k[x]=read();

				Link(x,x+k[x]>n?n+1:x+k[x]);

				break;

			}

		}

	}

	return 0;

}

\[\texttt{Thanks} \ \texttt{for} \ \texttt{watching}
\]

巴特西

题解【[HNOI2010]弹飞绵羊】

最新文章

热门文章