CF538H Summer Dichotomy 题解

自己做的 \ ^ w ^ /。

对于 \(m\) 个限制，我们得到了一个图，若不是二分图则无解，否则对于每个连通块有 \([l_1, r_1], [l_2, r_2]\) 的限制，表示对于两组的人数限制（注意此处 \(1, 2\) 并不代表组 \(1\)，\(2\)）。

不妨令 \(n_1\ge n_2, (r_1 > r_2 \operatorname{or} r_1 == r_2 \operatorname{and} l_1 < l_2)\)，则对于 \(l_1\ge l_2\)，必定是 \([l_1, r_1]\) 限制 \(n_1\)，\([l_2, r_2]\) 限制 \(n_2\)。

对于 \(l_1 < l_2\)，两者是包含关系，可能是以下两种之一：

1. \(n_1\in [l_1, r_1], n_2\in [l_2, r_2]\)
2. \(n_1\in [l_2, r_2], n_2\in [l_1, r_1]\)

因为 \(n_1\ge n_2\) 所以：

1. \(n_1\in [l_2, r_1], n_2\in [l_2, r_2]\)
2. \(n_1\in [l_2, r_2], n_2\in [l_1, l_2)\)

在二维平面上考虑限制，对于区间 1 与区间 2 不包含的是一个矩形，对于包含的是一个矩形挖掉右下角。

可以先求矩形的交，再挖掉右下角。

对于 \(t\le n_1 + n_2\le T\)，是两条 \(y = -x + b\) 的斜线，若矩形内有在两者中的，矩形的左/上边界必有其中的，而挖掉右下角对左/上边界影响最小，对于挖掉的维护矩形的左/上边界即可。

时间复杂度 \(\mathcal O(n)\)。

二分图染色的内容实现的不是很好。

code