月雩の小窝(损坏)
 
Made by 月雩 禁止转载(作者允许除外) | Theme: Fog
载入天数...
载入时分秒...
总访问量:  |   访问人数:
Copyright © 2020 pray-yueyu.github.io

洛谷 P2713:「罗马游戏」

  热度: loading...

[传送门]

星影落九天,鱼雁舞千弦。但为君沉吟,落日天涯圆。

题目描述

罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个人,每个人都是一个独立的团。最近举行了一次平面几何测试,每个人都得到了一个分数。 皇帝很喜欢平面几何,他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。 它可以发两种命令:

Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人,那么就忽略该命令。

Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了,这条命令就忽略。

皇帝希望他每发布一条kill命令,下面的将军就把被杀的人的分数报上来。(如果这条命令被忽略,那么就报0分)

输入格式

第一行一个整数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

输出格式
如果命令是Kill,对应的请输出被杀人的分数。(如果这个人不存在,就输出0)

输入输出样例

样例输入

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

样例输出

10
100
0
66

这是左偏树经典题目

但为什么大佬们都用左偏树啊 平板电视 它 不 香 吗

其实我不会左偏树(

不过话说这皇帝好残暴啊


对于q[i] (队列):q[i].first保存的是i的编号,q[i].second保存的是i的数值

对于vis[i]:判断编号为i的人是否被杀

对于Fa[i]:编号为i的人的集合中数值最小的人的编号(就是i的father)


对于每次操作:

①若操作为'M',先将i与j各自的father求出来

若编号为i或j的人已died或者i,j已在同一集合,则跳过此回合

反之就将i,j两个集合 合并

②若操作为'K',

若编号为i的人已去世,则跳过此回合

反之输出i所在集合father的值,并令它的vis为true(即已使用过)

最后将它(指i的father)弹出队列

Code:(为各位大佬献上我丑陋的代码~)

#include<bits/stdc++.h>
#define ll long long
#include <ext/pb_ds/priority_queue.hpp>//要使用pbds队列就要加这个头文件
using namespace std;
const int N=1000010;
int Fa[N],n,m,vis[N];
ll read()
{
	ll x=0,f=1;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;
}//没有丝毫作用的快读~
struct cmp
{
    bool operator()(pair<int,int>a,pair<int,int>b)
	{
        if(a.second == b.second)
			return a.first > b.first;
        return a.second > b.second;
    }
};//队列自动从小到大排序
int Get_F(int x){return Fa[x]==x?x:Fa[x]=Get_F(Fa[x]);}//并查集,路径压缩
__gnu_pbds::priority_queue <pair<int,int>,cmp> q[N];//前面的p__gnu_pbds::不能省!
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
	{
		int x=read();
		Fa[i]=i;
		q[i].push(make_pair(i,x));//第一个数是编号,第二个是值
	}//输入~
	int m=read();
	for(int i=1;i<=m;i++)
	{
		char ch[10];int x,y;
		scanf("%s",ch);
		if(ch[0]=='M')
		{
			x=read(),y=read();
			int x_0=Get_F(x),y_0=Get_F(y);//得到father
			if(vis[x]||vis[y]||x_0==y_0)continue;//判断是否可行
			q[x_0].join(q[y_0]);//将队列q[y_0]中所有值都加入q[x_0],并且会清空q[y_0]!
			Fa[y_0]=x_0;
		}//合并
		else
		{
			x=read();int x_0=Get_F(x);//得到father
			if(vis[x]){printf("0\n");continue;}//判断是否可行
			printf("%d\n",q[x_0].top().second);//输出
			vis[q[x_0].top().first]=true;//将被输出的人标记一下
			q[x_0].pop();//弹出
		}
	}
	return 0;	
} 
//**月雩·薇嫭**

题外:左偏树有什么用

还有就是,晚上肝题是真的爽

by:月雩·薇嫭 ,2020.8.5 0:16