Merging Towers
Contest: Educational Codeforces Round 91 (Rated for Div. 2)
Difficulty rating: 2300
Tags: data structures, dsu, implementation, trees

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.

Input format:
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).

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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]$$$.

Example input:
7 4
1 2 3 3 1 4 3
3 1
2 3
2 4

Example output:
5
4
2
0

Editorial:
First of all, let's try to find a simple way to evaluate the difficulty of a given set of towers. I claim that the difficulty is equal to the number of pairs of discs $$$(i, i + 1)$$$ that belong to different towers.
The beginning of the proof
• during each operation we can "merge" at most one such pair: if we move discs to the tower with disk $$$i$$$ on top of it, only the pair $$$(i - 1, i)$$$ can be affected;
• we can always take the first several $$$k$$$ discs belonging to the same tower and move them to the tower containing disc $$$k + 1$$$, thus merging exactly one pair in exactly one operation.
The end of the proof
After that, there are two main approaches: LCA and small-to-large merging. The model solution uses LCA, so I'll describe it.
For each pair $$$(i, i + 1)$$$, we have to find the first moment these discs belong to the same tower. To do so, let's build a rooted tree on $$$2m - 1$$$ vertices. The vertices $$$1$$$ to $$$m$$$ will be the leaves of the tree and will represent the original towers. The vertex $$$m + i$$$ will represent the tower created during the $$$i$$$-th query and will have two children — the vertices representing the towers we merge during the $$$i$$$-th query. The vertex $$$2m - 1$$$ is the root.
Now, if some vertex $$$x$$$ is an ancestor of vertex $$$y$$$, it means that the tower represented by vertex $$$x$$$ contains all the discs from the tower represented by vertex $$$y$$$. So, to find the first tower containing two discs $$$i$$$ and $$$i + 1$$$, we have to find the lowest common ancestor of the vertices representing the towers $$$t_i$$$ and $$$t_{i + 1}$$$. The easiest way to do it is to implement something like binary lifting, which allows us to solve the problem in $$$O(n \log m)$$$.