Skip to content

1125: 二哥的优先队列

题目

题目描述

二哥把所有女朋友候选人列了出来,一共有N组,编号为0~N-1。最开始的时候每组只有1个女生,每个女生有一个魅力值。二哥不断进行以下三种操作:

  1. 将一组并入另一组
  2. 将一组中魅力值最小的拿走
  3. 给某一组中添加一个女生

值得注意的是,如果X组在操作0中被并入其他组,那么二哥将不会再对X组进行这三种操作。

本题可以使用STL。

输入格式

第一行:N M$(0 \leq N,M \leq 300,000)$

分别表示最开始的组数与总的操作的次数

接下来N行

每行一个整数,表示最初0~N-1组中那个女生的魅力值

接下来M行

每行首先是一个整数,表示操作编号,0表示合并,1表示拿走魅力值最小的,2表示添加

对于操作0,跟着两个整数,a b,表示将编号为b的组并入编号为a的组(编号为b的组从此消失了)

对于操作1,跟着一个整数,a,表示讲编号为a的组中魅力值最小的女生拿走

对于操作2,跟着两个整数,a b,表示在编号为a的组中添加一个魅力值为b的女生

输出格式

对于每个操作1,输出一行,包含一个整数,表示被拿走的女生的魅力值(如果二哥妄图从一组已经没有人的组内拿走女生,请输出-1)

样例输入

5 9
0
36
49
98
3
1 4
0 2 4
1 1
0 0 3
1 0
0 1 2
0 0 1
2 0 15
1 0

样例输出

3
36
0
15

数据范围

大概用某种可合并优先队列

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!