← 返回题目列表

Codeforces · 1380/E

E. 合并塔

中文机器翻译题面 查看原题

您有一组 $$$n$$$ 圆盘,第 $$$i$$$ 圆盘的半径为 $$$i$$$。最初,这些圆盘被分成 $$$m$$$ 个塔:每个塔至少包含一个圆盘,每个塔中的圆盘从下到上按照半径降序排列。

您想组装一座包含所有这些圆盘的塔。为此,您可以选择两个不同的塔 $$$i$$$ 和 $$$j$$$(每个塔至少包含一个棋子),从塔 $$$i$$$ 中取出几个(可能是全部)顶部棋子,并将它们以相同的顺序放在塔 $$$j$$$ 的顶部,只要塔 $$$j$$$ 的顶部棋子比您移动的每个棋子都大。您可以多次执行此操作。

例如,如果您有两个塔,其中包含圆盘 $$$[6, 4, 2, 1]$$$ 和 $$$[8, 7, 5, 3]$$$(按从下到上的顺序),则只有两种可能的操作:

- 将圆盘 $$$1$$$ 从第一个塔移动到第二个塔,因此塔是 $$$[6, 4, 2]$$$ 和 $$$[8, 7, 5, 3, 1]$$$;
- 将棋盘 $$$[2, 1]$$$ 从第一个塔移动到第二个塔,因此塔是 $$$[6, 4]$$$ 和 $$$[8, 7, 5, 3, 2, 1]$$$。

令某组塔的难度为组装包含所有圆盘的一个塔所需的最少操作数。例如,塔组$$$[[3, 1], [2]]$$$的难度为$$$2$$$:您可以将圆盘$$$1$$$移动到第二个塔,然后将两个圆盘从第二个塔移动到第一个塔。

您收到 $$$m - 1$$$ 查询。每个查询由两个数字 $$$a_i$$$ 和 $$$b_i$$$ 表示,表示“合并塔 $$$a_i$$$ 和 $$$b_i$$$”(即从这两个塔中取出所有圆盘,并按照从上到下的半径降序组装一个包含所有圆盘的新塔)。生成的塔获得索引 $$$a_i$$$。

对于 [0, m - 1]$$$ 中的每个 $$$k,在执行第一个 $$$k$$$ 查询后计算塔组的难度。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le m \le n \le 2 \cdot 10^5$$$) — 分别是圆盘的数量和塔的数量。

第二行包含 $$$n$$$ 整数 $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ ($$$1 \le t_i \le m$$$),其中 $$$t_i$$$ 是 $$$i$$$ 所属塔盘的索引。从 $$$1$$$ 到 $$$m$$$ 的每个值在此序列中至少出现一次。

然后是 $$$m - 1$$$ 行,表示查询。每个查询由两个整数 $$$a_i$$$ 和 $$$b_i$$$ 表示($$$1 \le a_i, b_i \le m$$$, $$$a_i \ne b_i$$$),这意味着,在第 $$$i$$$ 查询期间,具有索引 $$$a_i$$$ 和 $$$b_i$$$ 的塔被合并($$$a_i$$$和 $$$b_i$$$ 的选择方式使得这些塔存在于第 $$$i$$$ 查询之前)。

输出

打印 $$$m$$$ 整数。第 $$$k$$$ 个整数($$$0$$$ 索引)应等于执行第一个 $$$k$$$ 查询后塔组的难度。

示例

输入 #1

7 4
1 2 3 3 1 4 3
3 1
2 3
2 4

输出 #1

5
4
2
0

注意

示例中的塔是:

- 查询之前:$$$[[5, 1], [2], [7, 4, 3], [6]]$$$;
- 第一个查询后:$$$[[2], [7, 5, 4, 3, 1], [6]]$$$;
- 第二次查询后:$$$[[7, 5, 4, 3, 2, 1], [6]]$$$;
- 第三次查询后,只有一座塔:$$$[7, 6, 5, 4, 3, 2, 1]$$$。