Tony Zhao

题目大意

请你维护N个集合，支持：

合并两个集合。
询问某个集合里面的最小值并删除它。

这题权值线段树卡空间所以只能用可并堆写qwq

可并堆，顾名思义就是可以快速合并的priority_queue.

不妨设x的键值$\ge$y的键值，那么我们将x的某个子树与y递归合并，并将合并后的堆设为x的子树。设点集X为以x为根的子树中遍历过的点，点集Y为以y为根的子树中遍历过的点，那么单次操作复杂度即为$O(|X|+|Y|)$

我忘记写特判了，之后调试了一整天……

真是GG呢qwq

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 1000010

int n,m,p[N],ls[N],rs[N],fa[N],rt[N],ix,iy,h[N];
char in[10];
bool killed[N];

inline int RI()
{
	int ret=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp>='0'&&tmp<='9') ret=ret*10+tmp-'0',tmp=getchar();
	return ret;
}

int unifind(int tx) {return fa[tx]==tx?tx:fa[tx]=unifind(fa[tx]);}

int merge(int lp,int rp)
{
	if(!lp) return rp;
	if(!rp) return lp;
	if(p[lp]>p[rp]) swap(lp,rp);
	rs[lp]=merge(rs[lp],rp);
	if(h[rs[lp]]>h[ls[lp]]) swap(ls[lp],rs[lp]);
	h[lp]=h[rs[lp]]?h[rs[lp]]+1:0;
	return lp;
}

int main()
{
	n=RI();
	for(int i=1;i<=n;++i) p[i]=RI(),fa[i]=i,rt[i]=i;
	m=RI();
	while(m--)
	{
		scanf("%s",in);
		if(in[0]=='M')
		{
			ix=RI(),iy=RI();
			if(killed[ix]||killed[iy]) continue;
			ix=unifind(ix),iy=unifind(iy);
			if(ix==iy)continue;
			fa[ix]=iy;
			rt[iy]=merge(rt[ix],rt[iy]);
		}
		if(in[0]=='K')
		{
			ix=RI();
			if(killed[ix])
			{
				printf("0\n");
				continue;
			}
			ix=unifind(ix);
			killed[rt[ix]]=true;
			printf("%d\n",p[rt[ix]]);
			rt[ix]=merge(ls[rt[ix]],rs[rt[ix]]);
		}
	}
}

BZOJ 1455 罗马游戏

题目大意