CF1380E Merging Towers

你有一组 $$$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$$$。 对于每个 $$$k \in [0, m - 1]$$$，计算执行前 $$$k$$$ 个查询后这组塔的难度。

第一行包含两个整数 $n$ 和 $m$（$2 \le m \le n \le 2 \cdot 10^5$）——分别是圆盘数量和塔的数量。 第二行包含 $n$ 个整数 $t_1, t_2, \dots, 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-indexed）应该等于执行前 $k$ 个查询后这组塔的难度。

样例中的塔为： - 查询前：$[[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]$。 翻译由 Deepseek-v4.1 Flash 完成。