#PQJ1876x9907. QOJ 1876_9907

    ID: 2741 传统题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2024深搜

QOJ 1876_9907

第一试最大匹配2(matching) IOI2025 中国国家集训队集中培训 最大匹配2(matching) 【题目描述】 给定长度为n 的整数序列a1, a2, · · · , an 和长度为n 的01 序列b1, b2, · · · , bn。 对于1 ≤i < j ≤n,称二元组(i, j) .构.成.匹.配当且仅当bi = 0 且bj = 1。 定义.极.大.匹.配.方.案Smax 为满足以下所有条件的二元组集合: • 对于任意(u, v) ∈Smax,1 ≤u < v ≤n 且(u, v) 构成匹配; • 每一个整数1 ≤i ≤n 在Smax 中出现至多一次; • 在满足以上条件的前提下,满足au = av 的二元组(u, v) 数量最多,即! (u,v)∈Smax[au = av] 最大; • 在满足以上条件的前提下,|Smax| 最大。 给定m 次修改,每次修改给出x, p, q,表示将(ax, bx) 修改为(p, q)。 你需要对于每个1 ≤i ≤m + 1 求出:按输入顺序依次进行前(i −1) 次操作后,极 大匹配方案Smax 的大小|Smax|。 【输入格式】 从标准输入读入数据。 输入的第一行两个整数n, m,表示序列长度和操作次数。 第二行n 个整数a1, a2, · · · , an 描述序列a。 第三行n 个整数b1, b2, · · · , bn 描述序列b。 接下来m 行每行三个整数x, p, q,描述一次修改。 【输出格式】 输出到标准输出。 输出m + 1 行,每行一个整数,第i 行表示按输入顺序依次进行前(i −1) 次操作 后|Smax| 的值。 【样例1 输入】 5 5 1 1 2 1 1 2 2 0 0 0 0 0 3 2 2 1 4 4 2 0 5 4 2 1 6 2 2 0 7 第4 页 共10 页 第一试最大匹配2(matching) IOI2025 中国国家集训队集中培训 1 1 1 8 【样例1 输出】 0 1 1 2 1 3 2 4 1 5 1 6 【样例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 = 1,b5 = 0,并不构 成匹配。 【样例2 输入】 10 10 1 2 1 2 2 2 2 1 2 2 2 2 1 1 0 0 0 0 1 0 0 0 3 3 2 0 4 5 1 0 5 9 1 1 6 4 2 1 7 8 1 1 8 2 1 0 9 1 2 1 10 8 2 0 11 1 1 1 12 9 1 0 13 第5 页 共10 页 第一试最大匹配2(matching) IOI2025 中国国家集训队集中培训 【样例2 输出】 1 1 1 2 1 3 2 4 3 5 3 6 4 7 4 8 3 9 3 10 2 11 【子任务】 对于所有测试数据, • 1 ≤n ≤2 × 105,0 ≤m ≤2 × 105; • 对于1 ≤i ≤n,1 ≤ai ≤n,0 ≤bi ≤1; • 每次修改中有1 ≤x ≤n,1 ≤p ≤n,0 ≤q ≤1。 Subtask 1(10%) : n ≤100, m = 0。 Subtask 2(15%) : n ≤2 × 103, m = 0。 Subtask 3(20%) : m = 0。 Subtask 4(15%) : ai, p ≤2。 Subtask 5(20%) : n, m ≤105。 Subtask 6(20%) : 无特殊限制。 第6 页 共10 页