题目描述

给定一个长度为 $n$ 的数组 $a$ 和 $q$ 个查询。我们还有一个无限长的二进制数组 $w$，初始时所有 $w_i = 1$。

共有三种类型的查询：

• $1 \ x$ —— 切换 $w_x$ 的值（从 $1$ 变为 $0$，或从 $0$ 变为 $1$）。
• $2 \ l \ r$ —— 统计数组 $a$ 中，满足 $w_{a_i} = 1$ 且 $l \le i \le r$ 的不同数字的数量。
• $3 \ x \ t$ —— 将 $a_x$ 的值赋为 $t$。

请对每个第二类查询给出答案。

输入格式

• 第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3\cdot10^5$）——数组的长度和查询的数量。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——数组元素的值。
• 接下来的 $q$ 行，每行以一个整数 $type$（$1 \le type \le 3$）开头，表示查询的类型：
  • 如果 $type = 1$，查询包含一个整数 $x$（$1 \le x \le 10^9$）——切换 $w_x$ 的值。
  • 如果 $type = 2$，查询包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$）——统计数组 $a$ 在区间 $[l, r]$ 中，满足 $w_{a_i} = 1$ 且 $l \le i \le r$ 的不同数字的数量。
  • 如果 $type = 3$，查询包含两个整数 $x$ 和 $t$（$1 \le x \le n, 1 \le t \le 10^9$）——将 $a_x$ 的值替换为 $t$。

输出格式

对于每个第二类查询，在单独一行输出区间内满足条件的不同数字的数量。

10 5
3 4 3 4 3 2 3 1 2 1
2 2 5
1 3
2 2 5
3 4 5
2 2 5

2
1
2

提示

在示例的第一个第二类查询中，区间为 $[4, 3, 4, 3]$，其中包含数字 $3$ 和 $4$，且 $w_3$、$w_4$ 均为 $1$，因此答案为 $2$。执行下一个类型 $1$ 的查询后，$w_3$ 变为 $0$，因此对于下一个查询，答案为 $1$。执行下一个查询后，数组变为 $[3, 4, 3, 5, 3, 2, 3, 1, 2, 1]$。在最后一个查询中，区间为 $[4, 3, 5, 3]$，包含数字 $3, 4, 5$，但 $w_3 = 0$，因此答案为 $2$。

评分细则

• （$8$ 分）：$n, q \le 10^3$；
• （$6$ 分）：仅包含类型 $2$ 的查询；$n = q$；$l_i = 1$；$r_i = i$；
• （$13$ 分）：仅包含类型 $2$ 的查询；
• （$10$ 分）：仅包含类型 $1$ 和 $2$ 的查询；所有 $a_i$ 互不相同；
• （$14$ 分）：仅包含类型 $1$ 和 $2$ 的查询；所有 $w_{a_i}$ 只能改变一次；
• （$7$ 分）：仅包含类型 $1$ 和 $2$ 的查询；
• （$14$ 分）：仅包含类型 $2$ 和 $3$ 的查询；
• （$8$ 分）：任何时刻 $a_i \le 100$；
• （$10$ 分）：$n, q \le 5\cdot10^4$；
• （$10$ 分）：无额外限制。

翻译由 DeepSeek V3 完成