Bzoj1455 罗马游戏

Posted by yjjr's blog on December 16, 2017

标签:左偏树(可并堆)

题目

题目传送门

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

部分数据如下 JudgeOnline/upload/201607/aa.rar

分析

要求一种数据结构:

  • 能够快速查询块内最小值

  • 合并操作

  • 删除操作

于是就想到了左偏树辣(别问我是怎么想到的)

左偏树裸题

code

#include<iostream>
#include<cstdio>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn=1e6+6;
struct tree{int l,r,w,d;}t[maxn];
int n,m,fa[maxn];
bool die[maxn];
char ch[10];
inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
 
int merge(int x,int y)
{
    if(x==0||y==0)return x+y;
    if(t[x].w>t[y].w)swap(x,y);
    t[x].r=merge(t[x].r,y);
    if(t[t[x].l].d<t[t[x].r].d)swap(t[x].l,t[x].r);
    t[x].d=t[t[x].r].d+1;
    return x;
}
     
int main()
{
    n=read();
    rep(i,1,n)t[i].w=read();
    m=read();
    t[0].d=-1;rep(i,1,n)fa[i]=i;
    rep(i,1,m){
        scanf("%s",ch);
        if(ch[0]=='M'){
            int x=read(),y=read();
            if(die[x]||die[y])continue;
            int r1=find(x),r2=find(y);
            if(r1!=r2){int t=merge(r1,r2);fa[r1]=fa[r2]=t;}
        }
        if(ch[0]=='K'){
            int x=read();
            if(die[x])printf("0\n");
            else{
                int r1=find(x);die[r1]=1;
                printf("%d\n",t[r1].w);
                fa[r1]=merge(t[r1].l,t[r1].r);fa[fa[r1]]=fa[r1];
            }
        }
    }
    return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr