题库练习 【模板】左偏树/可并堆
← 上一题 下一题 →

A2410 | 【模板】左偏树/可并堆

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

如题,一开始有 $n$ 个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作:

1. 1 x y:将第 $x$ 个数和第 $y$ 个数所在的小根堆合并(若第 $x$ 或第 $y$ 个数已经被删除或第 $x$ 和第 $y$ 个数在用一个堆内,则无视此操作)。

2. 2 x:输出第 $x$ 个数所在的堆最小数,并将这个最小数删除(若有多个最小数,优先删除先输入的;若第 $x$ 个数已经被删除,则输出 $-1$ 并无视删除操作)。

输入格式

第一行包含两个正整数 $n, m$,分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含 $n$ 个正整数,其中第 $i$ 个正整数表示第 $i$ 个小根堆初始时包含且仅包含的数。

接下来 $m$ 行每行 $2$ 个或 $3$ 个正整数,表示一条操作,格式如下:

操作 $1$:1 x y

操作 $2$:2 x

输出格式

输出包含若干行整数,分别依次对应每一个操作 $2$ 所得的结果。

输入输出样例

输入 #1
5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2
输出 #1
1
2
C++ 编辑器
输入
输出