[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$ **不是**颜色的编号上限。