A2262. 梦幻布丁
编程题
省选/NOI-
知识点
题目描述
$n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。
例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色.
例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色.
输入格式
第一行是两个整数，分别表示布丁个数 $n$ 和操作次数 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个布丁的颜色 $a_i$。
接下来 $m$ 行，每行描述一次操作。每行首先有一个整数 $op$ 表示操作类型：
- 若 $op = 1$，则后有两个整数 $x, y$，表示将颜色 $x$ 的布丁全部变成颜色 $y$。
- 若 $op = 2$，则表示一次询问。
第二行有 $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$ **不是**颜色的编号上限。
初始时布丁颜色依次为 $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$ **不是**颜色的编号上限。