AT_abc465_g [ABC465G] Sum of Mex of Mod of Linear

给定整数 $N, M, C, K$，以及一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。 共有 $Q$ 组查询，请按顺序处理。第 $q$ ($1\le q\le Q$) 次查询给定两个整数 $i_q, X_q$，在将 $A_{i_q}$ 修改为 $X_q$ 后，解决如下问题： > 计算 $\displaystyle \sum_{k=0}^{K-1} \mathop{\mathrm{mex}}\limits_{1 \le i \le N} \lbrace (Ck+A_i)\bmod M\rbrace$。其中，$\displaystyle \mathop{\mathrm{mex}}\limits_{1 \le i \le N} B_i$ 表示对于一个整数序列 $B = (B_1, B_2, \ldots, B_N)$，不存在于 $B$ 中的最小非负整数。

输入按如下格式从标准输入给出： > $N\ M\ C\ K$ > $A_1\ A_2\ \ldots\ A_N$ > $Q$ > $i_1\ X_1$ > $i_2\ X_2$ > $\vdots$ > $i_Q\ X_Q$

输出共 $Q$ 行。 第 $q$ ($1\le q\le Q$) 行输出处理完第 $q$ 次查询后的答案。

### 样例解释 1 第一次操作后，$A = (0,2)$，所求值为 $\text{mex}(\{0,2\})+\text{mex}(\{1,0\})=1+2=3$。 第二次操作后，$A = (1,2)$，所求值为 $\text{mex}(\{1,2\})+\text{mex}(\{2,0\})=0+1=1$。 第三次操作后，$A = (1,1)$，所求值为 $\text{mex}(\{1,1\})+\text{mex}(\{2,2\})=0+0=0$。 ### 数据范围 - $1\le N\le 2\times 10^5$ - $0\le C < M \le 10^9$ - $1\le K\le 10^9$ - $0\le A_i < M$ - $1\le Q\le 2\times 10^5$ - $1\le i_q \le N$ - $0\le X_q < M$ - 所有输入值均为整数。 由 ChatGPT 5 翻译