[HNOI2009] 梦幻布丁
题目描述
$n$ 个布丁摆成一行,进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色。
例如,颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色.
输入输出格式
输入格式
第一行是两个整数,分别表示布丁个数 $n$ 和操作次数 $m$。
第二行有 $n$ 个整数,第 $i$ 个整数表示第 $i$ 个布丁的颜色 $a_i$。
接下来 $m$ 行,每行描述一次操作。每行首先有一个整数 $op$ 表示操作类型:
- 若 $op = 1$,则后有两个整数 $x, y$,表示将颜色 $x$ 的布丁全部变成颜色 $y$。
- 若 $op = 2$,则表示一次询问。
输出格式
对于每次询问,输出一行一个整数表示答案。
输入输出样例
输入样例 #1
4 3
1 2 2 1
2
1 2 1
2
输出样例 #1
3
1
说明
### 样例 1 解释
初始时布丁颜色依次为 $1, 2, 2, 1$,三段颜色分别为 $[1, 1], [2, 3], [4, 4]$。
一次操作后,布丁的颜色变为 $1, 1, 1, 1$,只有 $[1, 4]$ 一段颜色。
### 数据规模与约定
对于全部的测试点,保证 $1 \leq n, m \leq 10^5$,$1 \leq a_i ,x, y \leq 10^6$。
### 提示
请注意,**不保证**颜色的编号不大于 $n$,也**不保证** $x \neq y$,$m$ **不是**颜色的编号上限。