#P18323. Matching Query

Matching Query

Matching Query

给定长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N),其中每个元素都在 00 到 M−1M-1 之间。

你需要依次处理 QQ 次修改。第 ii 次修改给定整数 xi,yix_i,y_i:

  1. 将 AxiA_{x_i} 改成 yiy_i。
  2. 根据修改后的序列构造一个有 NN 个顶点的无向图 GG。顶点编号为 11 到 NN。对于每一对 1≤u<v≤N1\le u<v\le N,当且仅当Au+1≡Av(modM)A_u+1\equiv A_v\pmod M 时,在顶点 u,vu,v 之间连一条无向边。
  3. 求出 GG 的最大匹配大小。

匹配是一些两两没有公共端点的边;匹配大小是其中边的条数。

**注意:**连边条件中的 u<vu<v 不能交换。图虽然是无向图,但判断是否连边时,使用的是编号较小顶点的值加 11,与编号较大顶点的值比较。

输入格式

第一行三个整数 N,M,QN,M,Q。

第二行 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

接下来 QQ 行,第 ii 行两个整数 xi,yix_i,y_i,描述第 ii 次修改。

输出格式

输出 QQ 行。第 ii 行一个整数,表示执行第 ii 次修改后,图 GG 的最大匹配大小。

数据范围

  • 2≤N≤3×1052\le N\le3\times10^5;
  • 2≤M≤3×1052\le M\le3\times10^5;
  • 1≤Q≤3×1051\le Q\le3\times10^5;
  • 0≤Ai<M0\le A_i<M;
  • 1≤xi≤N1\le x_i\le N;
  • 0≤yi<M0\le y_i<M;
  • 所有输入值均为整数。

样例

样例输入 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

说明

第一次修改后,A=(1,1,0,2,0,0)A=(1,1,0,2,0,0)。图中有边 (1,4),(2,4),(4,5),(4,6)(1,4),(2,4),(4,5),(4,6),最大匹配大小为 11。

第二次修改后,A=(1,1,0,1,0,0)A=(1,1,0,1,0,0)。图中只有边 (3,4)(3,4),最大匹配大小为 11。

Background

Special for beginners, ^_^

Description

Given two integers x and y, print the sum.

Format

Input

Two integers x and y, satisfying 0≤x,y≤327670\leq x,y\leq 32767 .

Output

One integer, the sum of x and y.

Samples

123 500
623

Limitation

1s, 1024KiB for each test case.