#P18323. Matching Query
Matching Query
Matching Query
给定长度为 的整数序列 ,其中每个元素都在 到 之间。
你需要依次处理 次修改。第 次修改给定整数 :
- 将 改成 。
- 根据修改后的序列构造一个有 个顶点的无向图 。顶点编号为 到 。对于每一对 ,当且仅当 时,在顶点 之间连一条无向边。
- 求出 的最大匹配大小。
匹配是一些两两没有公共端点的边;匹配大小是其中边的条数。
**注意:**连边条件中的 不能交换。图虽然是无向图,但判断是否连边时,使用的是编号较小顶点的值加 ,与编号较大顶点的值比较。
输入格式
第一行三个整数 。
第二行 个整数 。
接下来 行,第 行两个整数 ,描述第 次修改。
输出格式
输出 行。第 行一个整数,表示执行第 次修改后,图 的最大匹配大小。
数据范围
- ;
- ;
- ;
- ;
- ;
- ;
- 所有输入值均为整数。
样例
样例输入 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
说明
第一次修改后,。图中有边 ,最大匹配大小为 。
第二次修改后,。图中只有边 ,最大匹配大小为 。
Background
Special for beginners, ^_^
Description
Given two integers x and y, print the sum.
Format
Input
Two integers x and y, satisfying .
Output
One integer, the sum of x and y.
Samples
123 500
623
Limitation
1s, 1024KiB for each test case.