题解：AT_arc232_a [ARC232A] Two in the Range

ty_mxzhn · 2026-10-22 15:12:56 · 题解

你觉得你是题吗？

赛时做法：

首先排序之后扫一遍，假设 [x,y] \subseteq [l,r]，那么 [l,x-1] 和 [y+1,r] 全都是 0。把 [l,r] 丢掉。

这样剩下的区间只有相交和相离的关系。把剩下的区间排序并重新标号，把所有已经是 0 的位置删除。

转置一下，选择位置 i 赋值为 1，会导致一个区间的查询都被 +1，要让每个查询都是 2，也就是一个覆盖问题。

这个和 NOI D1T1 是差不多的，其实就是分成两组，每一组都是一些区间 [x,y]，能够不重不漏的覆盖 [1,m]。连边 x\to y+1，相当于找两条 1 到 m+1 的路径不经过重复的边。可以跑流。只要能够增广两次即可。