CF940F Machine Learning

你回到家，闻到一股难闻的气味。它来自哪里？ 给定一个数组 $a$，你需要回答以下两种查询： 1. 给定两个整数 $l$ 和 $r$。令 $c_{i}$ 表示 $a_{l:r}$ 中 $i$ 出现的次数，其中 $a_{l:r}$ 表示从第 $l$ 个元素到第 $r$ 个元素（包含两端）的子数组。请你求出集合 $\{c_{0},c_{1},...,c_{10^{9}}\}$ 的 Mex。 2. 给定两个整数 $p$ 和 $x$。将 $a_{p}$ 改为 $x$。 一个多重集合的 Mex 是指不在该集合中的最小非负整数。 注意，本题中数组 $a$ 的所有元素都是正整数，这意味着 $c_{0}=0$，因此对于第一类查询，答案永远不会是 $0$。

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 100000$），分别表示数组的长度和查询的数量。 第二行包含 $n$ 个整数，表示 $a_{1}, a_{2}, ..., a_{n}$（$1 \leq a_{i} \leq 10^{9}$）。 接下来的 $q$ 行，每行描述一个查询。 第一类查询由三个整数 $t_{i}=1$，$l_{i}$，$r_{i}$ 描述，其中 $1 \leq l_{i} \leq r_{i} \leq n$，表示子数组的区间。 第二类查询由三个整数 $t_{i}=2$，$p_{i}$，$x_{i}$ 描述，其中 $1 \leq p_{i} \leq n$ 表示要修改的元素下标，$1 \leq x_{i} \leq 10^{9}$ 表示新的值。

对于每个第一类查询，输出一个整数，表示集合 $\{c_{0},c_{1},...,c_{10^{9}}\}$ 的 Mex。

第一条查询的子数组只包含一个 $1$。 第二条查询的子数组包含四个 $2$，一个 $3$ 和两个 $1$。 第四条查询的子数组包含三个 $1$，三个 $2$ 和一个 $3$。 由 ChatGPT 4.1 翻译