【BZOJ-1455】罗马游戏 可并堆 （左偏树）

时间：2022-04-07 08:45:08

1455: 罗马游戏

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1355  Solved: 561
[Submit][Status][Discuss]

Description

罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个人，每个人都是一个独立的团。最近举行了一次平面几何测试，每个人都得到了一个分数。 皇帝很喜欢平面几何，他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。 它可以发两种命令： 1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人，那么就忽略该命令。 2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了，这条命令就忽略。 皇帝希望他每发布一条kill命令，下面的将军就把被杀的人的分数报上来。（如果这条命令被忽略，那么就报0分）

Input

第一行一个整数n（1<=n<=1000000）。n表示士兵数，m表示总命令数。 第二行n个整数，其中第i个数表示编号为i的士兵的分数。（分数都是[0..10000]之间的整数） 第三行一个整数m(1<=m<=100000) 第3+i行描述第i条命令。命令为如下两种形式： 1. M i j 2. K i

Output

如果命令是Kill，对应的请输出被杀人的分数。（如果这个人不存在，就输出0）

Sample Input

5
100 90 66 99 10
7
M 1 5
K 1
K 1
M 2 3
M 3 4
K 5
K 4

Sample Output

10
100
0
66

HINT

Source

Solution

可并堆裸题

三个性质：

[性质1] 节点的键值小于或等于它的左右子节点的键值。

[性质2] 节点的左子节点的距离不小于右子节点的距离。

[性质3] 节点的左子节点右子节点也是一颗左偏树。

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 1000010

int d[maxn],son[maxn][],a[maxn],n,fa[maxn],m;

bool dead[maxn];

int find(int x)

{

    if (fa[x]==x) return x; else return fa[x]=find(fa[x]);

}

int merge(int x,int y)

{

    if (!x) return y;

    if (!y) return x;

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

    son[x][]=merge(son[x][],y);

    if (d[son[x][]]>d[son[x][]]) swap(son[x][],son[x][]);

    d[x]=d[son[x][]]+;

    return x;

}

int main()

{

    n=read();

    for (int i=; i<=n; i++) a[i]=read();

    for (int i=; i<=n; i++) fa[i]=i;

    m=read(); d[]=-;

    for (int i=; i<=m; i++)

        {

            char opt[]; int x,y; scanf("%s",opt);

            if (opt[]=='M')

                {

                    x=read(),y=read(); int fx=find(x),fy=find(y),rt;

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

                    if (fx!=fy)

                        rt=merge(fx,fy),fa[fx]=fa[fy]=rt;

                }

            if (opt[]=='K')

                {

                    x=read(); int fx=find(x);

                    if (dead[x]) {puts("");continue;}

                    dead[fx]=; printf("%d\n",a[fx]);

                    fa[fx]=merge(son[fx][],son[fx][]);

                    fa[fa[fx]]=fa[fx];

                }

        }

    return ;

}

相关文章