P3201 [HNOI2009] Dream Pudding

There are $n$ puddings in a line, and we will perform $m$ operations. An operation may recolor all puddings of one color into another color, or ask how many color segments there are at the moment. For example, four puddings with colors $1, 2, 2, 1$ have $3$ color segments.

The first line contains two integers, the number of puddings $n$ and the number of operations $m$. The second line contains $n$ integers; the $i$-th integer is the color $a_i$ of the $i$-th pudding. Then there are $m$ lines, each describing one operation. Each line starts with an integer $op$ indicating the type: - If $op = 1$, then two integers $x, y$ follow, meaning recolor all puddings of color $x$ to color $y$. - If $op = 2$, it denotes a query.

For each query, output one integer on a single line, indicating the answer.

Sample 1 Explanation Initially the colors are $1, 2, 2, 1$, and the three color segments are $[1, 1], [2, 3], [4, 4]$. After one operation, the colors become $1, 1, 1, 1$, leaving only one segment $[1, 4]$. Constraints For all test points, it is guaranteed that $1 \leq n, m \leq 10^5$, $1 \leq a_i, x, y \leq 10^6$. Notes Please note that it is **not guaranteed** that color IDs are at most $n$, it is also **not guaranteed** that $x \neq y$, and $m$ is **not** an upper bound on color IDs. Translated by ChatGPT 5