UOJ Logo Universal Online Judge

UOJ

#926. 【清华集训2024】最大匹配 2

附件下载 统计

给定长度为 n 的整数序列 a1,a2,,an 和长度为 n01 序列 b1,b2,,bn

对于 1i<jn,称二元组 (i,j) 构成匹配当且仅当 bi=0bj=1

定义极大匹配方案 Smax 为满足以下所有条件的二元组集合:

  • 对于任意 (u,v)Smax1u<vn(u,v) 构成匹配;
  • 每一个整数 1inSmax 中出现至多一次;
  • 在满足以上条件的前提下,满足 au=av 的二元组 (u,v) 数量最多,即 (u,v)Smax[au=av] 最大;
  • 在满足以上条件的前提下,|Smax| 最大。

给定 m 次修改,每次修改给出 x,p,q,表示将 (ax,bx) 修改为 (p,q)

你需要对于每个 1im+1 求出:按输入顺序依次进行前 (i1) 次操作后,极大匹配方案 Smax 的大小 |Smax|

输入格式

从标准输入读入数据。

输入的第一行两个整数 n,m,表示序列长度和操作次数。

第二行 n 个整数 a1,a2,,an 描述序列 a

第三行 n 个整数 b1,b2,,bn 描述序列 b

接下来 m 行每行三个整数 x,p,q,描述一次修改。

输出格式

输出到标准输出。

输出 (m+1) 行,每行一个整数,第 i 行表示按输入顺序依次进行前 (i1) 次操作后 |Smax| 的值。

样例 #1

样例输入 #1

5 5
1 2 1 1 2
0 0 0 0 0
2 2 1
4 2 0
4 2 1
2 2 0
1 1 1

样例输出 #1

0
1
1
2
1
1

样例 1 解释

  • 初始情况,由于所有的 bi 都等于 0,因此没有二元组构成匹配,极大匹配方案的大小为 0,故第一行输出 0
  • 进行第一次修改后,b2=1,极大匹配方案为 {(1,2)},故第二行输出 1
  • 进行前三次修改后,序列 a[1,2,1,2,2],序列 b[0,1,0,1,0]。极大匹配方案为 {(1,2),(3,4)},故第四行输出 2。注意此时 (4,5)b4=1b5=0,并不构成匹配。

样例 #2

样例输入 #2

10 10
2 1 2 2 2 2 1 2 2 2
1 1 0 0 0 0 1 0 0 0
3 2 0
5 1 0
9 1 1
4 2 1
8 1 1
2 1 0
1 2 1
8 2 0
1 1 1
9 1 0

样例输出 #2

1
1
1
2
3
3
4
4
3
3
2

子任务

对于所有测试数据,

  • 1n2×1050m2×105
  • 对于 1in1ain0bi1
  • 每次修改中有 1xn1pn0q1

  • Subtask 1(10%):n100m=0
  • Subtask 2(15%):n2×103m=0
  • Subtask 3(20%):m=0
  • Subtask 4(15%):ai,p2
  • Subtask 5(20%):n,m105
  • Subtask 6(20%):无特殊限制。