#1286. 【模板】可并堆 1

【模板】可并堆 1

题目描述

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

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

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

输入格式

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

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

接下来 mm 行每行 22 个或 33 个正整数,表示一条操作,格式如下:

操作 11:1 x y

操作 22:2 x

输出格式

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

样例

5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2
1
2

题目来源:洛谷 P3377