P12485 [集训队互测 2024] PM 大师

小 C 正在堆尸解隐藏曲的时候，他的好朋友小 A 随手就 Pure Memory 了。 小 C 也想成为像小 A 一样的 PM 大师，所以他需要你解决一个关于 PM（Prefix Mex）的问题。

__注意，本题对 $\operatorname{mex}$ 的定义与一般的定义不同。__ 对于可重集 $S$ 定义 $\operatorname{mex}(S)$ 表示最小的 __正整数__ $x$ 满足 $x\notin S$。 对于给定的数组 $a_1,a_2,\dots,a_n$，保证 $-1\le a_i\le n$，使用以下的方式生成数组 $b_1,b_2,\dots,b_n$： $$ b_i=\begin{cases}a_i&a_i\ne 0\\ \operatorname{mex}(\{b_1,b_2,\dots,b_{i-1}\})&a_i=0\end{cases} $$ 现在给定长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$，__保证初始时 $a_i\in \{-1,0\}$ 且数组 $a$ 不全为 $0$__。 给定 $q$ 次操作，每次操作给定三个整数 $x,k,y$，保证 $1\le x,y\le n$，$a_x\ne 0$，$-1\le k\le n$ 且 $k\ne 0$。表示先将 $a_x$ 修改为 $k$，然后你需要求出使用当前的数组 $a$ 所生成的数组 $b$ 中 $b_y$ 的值。 __注意，任意时刻为 $0$ 的 $a_i$ 不会被修改，不为 $0$ 的 $a_i$ 不会被修改为 $0$。__

第一行两个正整数 $n,q$。 第二行 $n$ 个整数，描述 $a_1,a_2,\dots,a_n$，保证初始时 $a_i\in \{-1,0\}$ 且数组 $a$ 不全为 $0$。 接下来 $q$ 行，每行 $3$ 个整数 $x,k,y$，描述一次操作。

共 $q$ 行，第 $i$ 行输出一个整数表示使用第 $i$ 次修改操作后的数组 $a$ 所生成的数组 $b$ 中 $b_y$ 的值。

__样例 2：__ 见下发文件，其满足子任务 $1$ 的限制。 ### 数据范围 对于 $100\%$ 的数据，保证 $1\le n,q\le 10^6$，$a_i\in \{-1,0\}$，$1\le x,y\le n$，$a_x\ne 0$，$-1\le k\le n$ 且 $k\ne 0$。保证数组 $a$ 不全为 $0$。 | 子任务编号 | 特殊性质 | 分值 | | :--------: | :------------------------------: | ---- | | $1$ | $n,q\le 10^4$ | $10$ | | $2$ | 初始时序列 $a$ 单调不降 | $10$ | | $3$ | $k\le 100$ | $10$ | | $4$ | 序列 $a$ 中 $0$ 的数量 $\le 100$ | $10$ | | $5$ | 每次修改前 $a_x=-1$ | $30$ | | $6$ | 无 | $30$ |