【中山纪念中学六年级模拟赛】纸人 题解

题目大意

有 \(n\) 个纸人，有三种操作

• C x y ，把 \(x\) 所在队列接到 \(y\) 所在队列后面
• F x 烧掉 \(x\) 和 \(x\) 后面的纸人
• Q x 询问 \(x\) 所在队列的队头、队尾，若 \(x\) 被烧，输出 -1

可能出现烧掉烧掉的纸人，或者将烧掉的纸人合并，请自动忽略

Sample Input

5 9
C 1 2
C 2 3
Q 2
C 4 5
Q 4
F 2
Q 3
C 4 3
Q 3

Sample Output

3 1
5 4
3 3
3 4

题解

用并查集，可以暴力烧纸人

因为烧是连续的，不会重复，所以每个纸人只会烧 1 次，均摊 \(O(n)\)

其他两个操作，用并查集维护最后点即可

Code

#include<bits/stdc++.h>
using namespace std;
inline int Rd() {
	register int x=0;
	char C=getchar();
	for(;C<'0'||C>'9';C=getchar()) ;
	for(;C>'/'&&C<':';C=getchar()) x=(x<<1)+(x<<3)+(C^48);
	return x;
}
const int N=500005; 
int n,T,vis[N],fa[N],ls[N],rf[N],ff[N];
char opt;
int fnd(int x) { return fa[x]==x?x:fa[x]=fnd(fa[x]); }
void fre(int x) { vis[x]=1; if(rf[x]^x && !vis[rf[x]])fre(rf[x]); }
int main() {
	// freopen("e.in","r",stdin);
	// freopen("e.out","w",stdout);
	n=Rd(),T=Rd();
	for(int i=1;i<=n;i++)
		ff[i]=fa[i]=rf[i]=ls[i]=i;
	for(int x,y,p,q;T--;) {
		do opt=getchar();while(opt<'A'||opt>'Z');
		x=Rd();
		if(opt=='Q') {
			if(vis[x])puts("-1");
			else printf("%d %d\n",fnd(x),ls[fnd(x)]);
		} else if(opt=='C') {
			y=Rd();
			if(vis[x] || vis[y])continue;
			p=fnd(x),q=fnd(y);
			if(p==q)continue;
			rf[ls[q]]=p,ff[p]=ls[q];
			fa[p]=q,ls[q]=ls[p];
		} else {
			if(!vis[x])
			ls[fnd(ff[x])]=ff[x],fre(x);
		}
	}
}