P15094 [UOI 2025 II Stage] Three Queries

给定一个长度为 $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$。

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

在示例的第一个第二类查询中，区间为 $[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 完成