#P3377. 【模板】左偏树/可并堆

【模板】左偏树/可并堆

题目描述

如题,一开始有 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 个正整数,表示一条操作,格式如下:

操作 111 x y

操作 222 x

输出格式

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

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

提示

【数据规模】

对于 30%30\% 的数据:n10n\le 10m10m\le 10
对于 70%70\% 的数据:n103n\le 10^3m103m\le 10^3
对于 100%100\% 的数据:n105n\le 10^5m105m\le 10^5,初始时小根堆中的所有数都在 int 范围内。

【样例解释】

初始状态下,五个小根堆分别为:{1}\{1\}{5}\{5\}{4}\{4\}{2}\{2\}{3}\{3\}

第一次操作,将第 11 个数所在的小根堆与第 55 个数所在的小根堆合并,故变为四个小根堆:{1,3}\{1,3\}{5}\{5\}{4}\{4\}{2}\{2\}

第二次操作,将第 22 个数所在的小根堆与第 55 个数所在的小根堆合并,故变为三个小根堆:{1,3,5}\{1,3,5\}{4}\{4\}{2}\{2\}

第三次操作,将第 22 个数所在的小根堆的最小值输出并删除,故输出 11,第一个数被删除,三个小根堆为:{3,5}\{3,5\}{4}\{4\}{2}\{2\}

第四次操作,将第 44 个数所在的小根堆与第 22 个数所在的小根堆合并,故变为两个小根堆:{2,3,5}\{2,3,5\}{4}\{4\}

第五次操作,将第 22 个数所在的小根堆的最小值输出并删除,故输出 22,第四个数被删除,两个小根堆为:{3,5}\{3,5\}{4}\{4\}

故输出依次为 1122