C++ 解法, 执行用时: 549ms, 内存消耗: 21424K, 提交时间: 2022-07-27 17:38:37

#include<iostream>
using namespace std;

int n,m,a[1000010],d[1000010],ls[1000010],rs[1000010],f[1000010],x,y;
bool b[1000010];
char z;
int find(int x){
	if(f[x]==x)
	return x;
	return f[x]=find(f[x]);
}
int merge(int x,int y){
	if(!x||!y)
		return x+y;
	if(a[x]>a[y]||(a[x]==a[y]&&x>y))
		swap(x,y);
	rs[x]=merge(rs[x],y);
	if(d[ls[x]]<d[rs[x]])
		swap(ls[x],rs[x]);
	d[x]=d[rs[x]]+1;
	return x;
}
int main(){
	cin>>n;
	d[0]=-1;
	for(int i=1;i<=n;i++){
		f[i]=i;
		cin>>a[i];
	}
	cin>>m; 
	while(m--){
		cin>>z;
		if(z=='M'){
			cin>>x>>y;
			if(b[x]||b[y])
				continue;
			x=find(x);
			y=find(y);
			if(x==y)
				continue;
			f[x]=f[y]=merge(x,y);
		}
		else if(z=='K'){
			cin>>x;
			if(b[x]){
				cout<<0<<endl;
				continue;
			}
			x=find(x);
			cout<<a[x]<<endl;
			b[x]=1;
			f[x]=f[ls[x]]=f[rs[x]]=merge(ls[x],rs[x]);
			ls[x]=rs[x]=d[x]=0;
		}
	}
	return 0;
}