LINK：罗马游戏
这道题 每次合并两个集合 或者 每次找到某个集合中值最小的并且将其删掉。
发现直接主席树+主席树合并即可 但是这样做过于不优美且(nleq 1000000)这样做在常数上不优秀。
我们考虑开堆 合并两个堆？启发式合并？nlog^2崩掉。
那直接开斜堆 即左偏树 或者说可并堆。这样合并常数小 且是log的。
外面套一个并查集即可。
简单复习一下左偏树的几个性质。
每个节点一般有5个元素 左儿子 右儿子 权值 编号 距离。是一个二叉树。
如果维护的是小根堆的话 显然 父亲比儿子权值小。
距离的定义是 离叶子节点的最近距离。
由于是左偏树 所以左儿子距离大于等于右儿子距离。
所以父亲距离由右儿子提供。
树高log 合并log。插入 log。
code：
const int MAXN=1000010;
int n,m,ans;
int f[MAXN],vis[MAXN],d[MAXN];
char a[2];
struct wy
{
int l,r;
int v;
}t[MAXN];
inline int getfather(int x){return x==f[x]?x:f[x]=getfather(f[x]);}
inline int merge(int x,int y)
{
if(!x||!y)return x|y;
if(t[x].v>t[y].v)swap(x,y);
t[x].r=merge(t[x].r,y);
if(d[t[x].r]>d[t[x].l])swap(t[x].l,t[x].r);
d[x]=d[t[x].r]+1;
return x;
}
inline void K(int x)
{
vis[x]=1;
int w=merge(t[x].l,t[x].r);
f[w]=w;f[x]=w;ans=t[x].v;
}
int main()
{
freopen("1.in","r",stdin);
get(n);rep(1,n,i)t[i]=(wy){0,0,read()},f[i]=i;
get(m);
rep(1,m,i)
{
int x,y;
gtc(a);
if(a[1]=='M')
{
get(x);get(y);
if(vis[x]||vis[y])continue;
int xx=getfather(x);
int yy=getfather(y);
if(xx==yy)continue;
int w=merge(xx,yy);
f[xx]=w;f[yy]=w;
}
else
{
get(x);
if(vis[x]){put(0);continue;}
int xx=getfather(x);
K(xx);put(ans);
}
}
return 0;
}