← 返回题目列表

AtCoder · abc465_g

G. 线性 Mod 的 Mex 之和

中文机器翻译题面 查看原题

分数: 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