BZOJ 1455 罗马游戏

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1455

题意:略。

思路:左偏树模板题,这里盗用下黄学长的总结:左偏树的性质:1.【堆性质】:节点的关键字大等于其儿子节点的关键字;2.【左偏性质】:定义节点到最近的叶节点的距离为节点距离,任意节点的左儿子的距离大于右儿子的距离。左偏树在实现插入操作时总是从右侧插入,也就是总是让短的一侧生长,如果右侧长于左侧,那么交换左右侧,继续从右侧生长。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1000000+5;
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
char op[10];
int n,m,fa[maxn],l[maxn],r[maxn],d[maxn],v[maxn];
bool die[maxn];
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
int Merge(int x,int y){
    if (!x) return y;
    if (!y) return x;
    if (v[x]>v[y]) swap(x,y);
    r[x]=Merge(r[x],y);
    if (d[r[x]]>d[l[x]]) swap(l[x],r[x]);
    d[x]=d[r[x]]+1;
    return x;
}
int main(){
    read(n);
    for (int i=1;i<=n;i++) read(v[i]),fa[i]=i;
    d[0]=-1;
    for (read(m);m--;){
        scanf("%s",op);int x,y;
        if (op[0]=='M'){
            read(x),read(y);
            if (die[x]||die[y])continue;
            int tx=Find(x),ty=Find(y);
            if (tx!=ty){
                fa[tx]=fa[ty]=Merge(tx,ty);
            }
        }
        else{
            read(x);
            if (die[x]) puts("0");
            else{
                int tx=Find(x);die[tx]=true;
                printf("%d\n",v[tx]);
                fa[tx]=Merge(l[tx],r[tx]);
                fa[fa[tx]]=fa[tx];//他自己为根
            }
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注