luogu P2713 罗马游戏

思路

模拟就好
左偏树合并
并查集寻找

代码

#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;
}