分数: 625 点
问题陈述
给你整数 N,M,C,K 和一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.
你被给予 Q 查询,您应按顺序处理。的 q-th (1\le q\le Q) 查询给出整数 i_q,X_q,更改后应该解决以下问题 A_{i_q} to 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=(B_1,B_2,\ldots,B_N).
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
2 3 1 2 0 2 3 2 2 1 1 2 1
示例输出 1
3 1 0
第一个查询集 A=(0,2)。寻求的值为 \displaystyle \text{mex}(\lbrace 0,2\rbrace)+\text{mex}(\lbrace 1,0\rbrace)=1+2=3.
第二个查询集 A=(1,2)。寻求的值为 \displaystyle \text{mex}(\lbrace 1,2\rbrace)+\text{mex}(\lbrace 2,0\rbrace)=0+1=1.
第三个查询集 A=(1,1)。寻求的值为 \displaystyle \text{mex}(\lbrace 1,1\rbrace)+\text{mex}(\lbrace 2,2\rbrace)=0+0=0.
示例输入 2
7 9 3 19 7 0 2 8 1 3 4 7 3 5 1 6 3 2 5 5 4 7 7 8 2 4
示例输出 2
32 44 53 37 49 37 54