Luogu

BZOJ(权限题)

分析

左偏树板子。

M操作就是合并两个堆。

K操作就是取出堆中最小的数,然后pop()一下。

特判一下K操作时Kill了一个已死的人的情况,此时输出0

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000000+10;

int n,m;
int fa[MAXN],v[MAXN],ch[MAXN][2],dis[MAXN];

inline int find(int x) {
    while (fa[x]) x=fa[x];
    return x;
}

inline int merge(int x,int y) {
    if (!x||!y) return x+y;
    if (v[x]>v[y]||(v[x]==v[y]&&x>y)) swap(x,y);
    ch[x][1]=merge(ch[x][1],y);
    fa[ch[x][1]]=x;
    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;
}

inline void pop(int x) {
    v[x]=-1;
    fa[ch[x][0]]=fa[ch[x][1]]=0;
    merge(ch[x][0],ch[x][1]);
}

int main() {
    dis[0]=-1;
    n=read();
    for (re int i=1;i<=n;++i) v[i]=read();
    m=read();
    for (re int i=1;i<=m;++i) {
        char op[2]; scanf("%s",op);
        if (op[0]=='M') { //合并
            int x=read(),y=read();
            if (v[x]==-1||v[y]==-1) continue;
            x=find(x),y=find(y);
            if (x!=y) merge(x,y);
        } else { //删除
            int x=read();
            if (v[x]==-1) puts("0");
            else {
                x=find(x);
                printf("%d\n",v[x]);
                pop(x);
            }
        }
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 42 PM