配点 : {100} 点
問題文
0 以上 M 的整数组成 N 整数序列 给出 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 的顶点 u,v\ (1\leq u\lt v\leq N) 当 A_u+1\equiv A_v\ (\mathrm{mod}\ M) 成立时,边被拉伸。 求 G 的最大匹配大小。
制約
- 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\lt M
- 1\leq x_i\leq N
- 0\leq y_i\lt M
- 所有输入均为整数
部分点
这个问题有多个部分点。 如果正确答案是满足
- 附加限制 如果正确答案是满足 Q=1 的数据集 给出 10 点。 如果您正确回答了所有满足
- 附加限制 如果正确答案是满足 M\leq 100 的数据集 给出 10 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
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 输出查询的答案。 对于第
入力例 1
6 3 5 1 1 0 2 0 2 6 0 4 1 5 2 1 2 6 2
出力例 1
1 1 2 3 3
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 。