P10208 [JOI 2024 Final] 礼物交换 题解

· · 题解

考虑什么样的区间是合法的。

题目很二分图。不妨将 A 看成左部点，B 看成右部点。每次询问的区间 [l,r] 中，对于所有 i\in[l,r]，A_i 向所有满足 j\in[l,i)\cup(i,r],A_i>B_j 的 B_j 连边，答案等价于是否有完美匹配。

将 A 与 B 放在一起从小到大排序，若最后排出来的形式为 \underbrace{BABABBA\dots}_{k个A,k个B}B_xA_x\dots 必然无解。每个 A_i 对一个前缀里的所有 B 连边然后删掉边 (A_i,B_i)。根据 hall 定理，这 k 个 A 与 A_x 的邻集大小为 k<k+1，则不存在完美匹配。

发现好像构造不出来其他的无解形式了，尝试归纳上述情况：存在 i 满足 B_i,A_i 相邻且 B_i 之前的 A 与 B 数量相等。

由于 B_i<A_i，则排序之后的形式必然是一个合法的括号匹配，不考虑删边，始终有 \lvert S\rvert\leq\lvert T\rvert（T 为 S 的邻集）；删除 (A_i,B_i) 后，有 \lvert S\rvert\leq\lvert T\rvert+1，当且仅当在上述情况时取等。

有了结论后，实现是简单的。

将第 i 个学生看成区间 [B_i,A_i]，结论等价于存在一个区间与其他区间的交集为空。预处理 L_i,R_i 分别表示 i 左边最近的与 i 有交的区间， i 右边最近的与 i 有交的区间（不存在则分别为极小/极大值），合法要求 \forall i\in[l,r],[l,r]\notin(L_i,R_i)。

求 L_i,R_i 是区间覆盖求极值，判合法可以离线扫描线，时间复杂度 O((N+Q)\log N)。

Code