思路

模拟就好

左偏树合并

并查集寻找

代码

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

const int maxn=1000005;

int read() {

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

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

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

	return x*f;

}

int n,m,f[maxn],rt[maxn];

bool vis[maxn];

int ch[maxn][2],val[maxn],dis[maxn];

int merge(int x,int y) {

	if(!x || !y) return x+y;

	if(val[x]>val[y]) swap(x,y);

	ch[x][0]=merge(ch[x][0],y);

	if(dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][0],ch[x][1]);

	dis[x]=dis[ch[x][1]]+1;

	return x;

}

int find(int x) {return x==f[x] ? x : f[x]=find(f[x]);}

int main() {

	n=read();

	FOR(i,1,n) {

		val[i]=read();

		rt[i]=f[i]=i;

	}

	m=read();

	FOR(i,1,m) {

		char s[10];

		scanf("%s",s);

		if(s[0]=='M') {

			int a=read(),b=read();

			if(vis[a]||vis[b]) continue;

			int fa=find(a),fb=find(b);

			if(fa==fb) continue;

			f[fb]=fa;

			rt[fa]=merge(rt[fa],rt[fb]);

		} else {

			int a=read();

			if(vis[a]) {

				cout<<"0\n";

			 	continue;

			}

			int fa=find(a);

			cout<<val[rt[fa]]<<"\n";

			vis[rt[fa]]=1;

			rt[fa]=merge(ch[rt[fa]][0],ch[rt[fa]][1]);

		}

	}

	return 0;

}