BZOJ1455罗马游戏

左偏树裸题。

题面描述让人意识到了平面几何的重要性。

//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<queue>

#include<ctime>

#include<cmath>

const int N=;

typedef long long LL;

using namespace std;

char o[];

template<typename T> void read(T &x) {

    char ch=getchar(); x=; T f=;

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

int n,m,rt[N],v[N],ch[N][],die[N],fa[N],dis[N];

#define lc ch[x][0]

#define rc ch[x][1]

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

int merge(int x,int y) {

    if(!(x*y)) return x^y;

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

    rc=merge(rc,y);

    if(dis[lc]<dis[rc]) swap(lc,rc);

    if(!rc) dis[x]=;

    else dis[x]=dis[rc]+;

    return x;

}

int main() {

#ifdef DEBUG

    freopen(".in","r",stdin);

    freopen(".out","w",stdout);

#endif

    read(n);

    for(int i=;i<=n;i++) {rt[i]=i; fa[i]=i; read(v[i]);}

    read(m);

    while(m--) {

        int x,y;

        scanf("%s",o);

        if(o[]=='K') {

            read(x);

            if(die[x]) {printf("0\n"); continue;}

            y=find(x);

            printf("%d\n",v[rt[y]]);

            die[rt[y]]=;

            rt[y]=merge(ch[rt[y]][],ch[rt[y]][]);

        }

        else {

            read(x); read(y);

            if(die[x]||die[y]) continue;

            int u=find(x),v=find(y);

            if(u!=v) {

                fa[u]=rt[v];

                rt[v]=merge(rt[v],rt[u]);

            }

        }

    }

    return ;

}