AT_tupc2024_b Matching Query

给定一个长度为 $N$、元素为 $0$ 及以上且小于 $M$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。 接下来有 $Q$ 个询问，请按顺序处理。第 $i$ 个询问如下所述： - 给定整数 $x_i, y_i$，将 $A$ 的第 $x_i$ 个元素更新为 $y_i$。然后，解决以下问题。 - 以整数序列 $A$ 为基础，构建一个有 $N$ 个顶点的无向图 $G$。顶点编号为 $1,2,\ldots,N$。对于任意 $1\leq u< v\leq N$，当 $A_u+1\equiv A_v\pmod{M}$ 时，在顶点 $u$ 和 $v$ 之间连一条边。请输出 $G$ 的最大匹配的大小。

输入按以下格式从标准输入给出。 > $N$ $M$ $Q$ $A_1$ $A_2$ $\ldots$ $A_N$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_Q$ $y_Q$

输出 $Q$ 行。第 $i$ 行输出第 $i$ 次询问的答案。

## 部分分 本题设有多个部分分。 - 对于额外限制 $Q=1$ 的数据集，答对可得 $10$ 分。 - 对于额外限制 $M\leq 100$ 的数据集，答对可得 $10$ 分。 ## 样例解释 1 对于第 $1$ 次询问，$A_6$ 被更新为 $0$，此时 $A=(1,1,0,2,0,0)$。在 $G$ 中，顶点 $1,4$ 之间、$2,4$ 之间、$4,5$ 之间和 $4,6$ 之间均有边，因此 $G$ 的最大匹配的大小为 $1$。 对于第 $2$ 次询问，$A_4$ 被更新为 $1$，此时 $A=(1,1,0,1,0,0)$。在 $G$ 中仅有顶点 $3,4$ 之间有边，因此 $G$ 的最大匹配的大小为 $1$。 # 数据范围 - $2\leq N\leq 3\times 10^5$ - $1\leq Q\leq 3\times 10^5$ - $2\leq M\leq 3\times 10^5$ - $0\leq A_i < M$ - $1\leq x_i \leq N$ - $0\leq y_i < M$ - 所有输入均为整数。 由 ChatGPT 5 翻译