Merging Towers

题意翻译

有 $n$ 个唱片，第 $i$ 个唱片半径是 $i$，最开始他们被摆放在 $m$ 个塔。每个塔的唱片高度由下到上递减，也就是半径大的唱片摆在塔的下面。 你的目标是把所有唱片摆放到某个塔上，你可以选择两个**非空**的塔，取出一个塔的上层某些(可以是所有的)唱片并摆放到另一个塔上，注意摆放完不能破坏塔的从下到上递减的性质。这个操作会产生 $1$ 的代价。 给出 $m-1$ 个操作，第 $i$ 个给出序号为 $a_i$ 和 $b_i$ 的塔。你需要在第 $i$ 个询问时回答：前 $i$ 次操作执行完之后，合并当前所有塔需要的最小代价。 ## 输入格式 第一行 $n,m$ 表示唱片的数量和塔的数量。 接下来 $n$ 个数 $t_i$ 表示第 $i$ 个唱片所在的塔的编号。 接下来 $m-1$ 行每行两个数 $a_i,b_i$ 表示一个询问。 ## 输出格式 输出 $m$ 行，每行对应第 $0\le i \le m-1$ 次询问的答案。 ## 数据范围 $2\le m\le n\le 2\cdot 10^5$ $1\le a_i,b_i\le m$ ，保证操作前 $a_i,b_i$ 塔存在唱片 $t_i$ 保证 $[1,m]$ 的数每个都会出现

题目描述

You have a set of $ n $ discs, the $ i $ -th disc has radius $ i $ . Initially, these discs are split among $ m $ towers: each tower contains at least one disc, and the discs in each tower are sorted in descending order of their radii from bottom to top. You would like to assemble one tower containing all of those discs. To do so, you may choose two different towers $ i $ and $ j $ (each containing at least one disc), take several (possibly all) top discs from the tower $ i $ and put them on top of the tower $ j $ in the same order, as long as the top disc of tower $ j $ is bigger than each of the discs you move. You may perform this operation any number of times. For example, if you have two towers containing discs $ [6, 4, 2, 1] $ and $ [8, 7, 5, 3] $ (in order from bottom to top), there are only two possible operations: - move disc $ 1 $ from the first tower to the second tower, so the towers are $ [6, 4, 2] $ and $ [8, 7, 5, 3, 1] $ ; - move discs $ [2, 1] $ from the first tower to the second tower, so the towers are $ [6, 4] $ and $ [8, 7, 5, 3, 2, 1] $ . Let the difficulty of some set of towers be the minimum number of operations required to assemble one tower containing all of the discs. For example, the difficulty of the set of towers $ [[3, 1], [2]] $ is $ 2 $ : you may move the disc $ 1 $ to the second tower, and then move both discs from the second tower to the first tower. You are given $ m - 1 $ queries. Each query is denoted by two numbers $ a_i $ and $ b_i $ , and means "merge the towers $ a_i $ and $ b_i $ " (that is, take all discs from these two towers and assemble a new tower containing all of them in descending order of their radii from top to bottom). The resulting tower gets index $ a_i $ . For each $ k \in [0, m - 1] $ , calculate the difficulty of the set of towers after the first $ k $ queries are performed.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ m $ ( $ 2 \le m \le n \le 2 \cdot 10^5 $ ) — the number of discs and the number of towers, respectively. The second line contains $ n $ integers $ t_1 $ , $ t_2 $ , ..., $ t_n $ ( $ 1 \le t_i \le m $ ), where $ t_i $ is the index of the tower disc $ i $ belongs to. Each value from $ 1 $ to $ m $ appears in this sequence at least once. Then $ m - 1 $ lines follow, denoting the queries. Each query is represented by two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i, b_i \le m $ , $ a_i \ne b_i $ ), meaning that, during the $ i $ -th query, the towers with indices $ a_i $ and $ b_i $ are merged ( $ a_i $ and $ b_i $ are chosen in such a way that these towers exist before the $ i $ -th query).

输出格式

Print $ m $ integers. The $ k $ -th integer ( $ 0 $ -indexed) should be equal to the difficulty of the set of towers after the first $ k $ queries are performed.

输入输出样例

输入样例 #1

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

输出样例 #1

5
4
2
0

说明

The towers in the example are: - before the queries: $ [[5, 1], [2], [7, 4, 3], [6]] $ ; - after the first query: $ [[2], [7, 5, 4, 3, 1], [6]] $ ; - after the second query: $ [[7, 5, 4, 3, 2, 1], [6]] $ ; - after the third query, there is only one tower: $ [7, 6, 5, 4, 3, 2, 1] $ .