← 返回题目列表

AtCoder · tupc2024_b

B. 匹配查询

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

配点 : {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 。