自动搬运

查看原文

来自洛谷，原作者为

	Perta broken tower

搬运于2025-08-24 22:55:46，当前版本为作者最后更新于2024-03-20 10:39:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

题目很二分图。不妨将 $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