ARC142E 题解

首先对于一对限制 $(x,y)$，形象来说就是能不能将 $a_x,a_y$ 与 $b_x,b_y$ 配对，使得 $a_x \ge b_{tox}$，$a_y \ge b_{toy}$。也即 $\min(a_x,a_y) \ge \min(b_x,b_y)$，$\max(a_x,a_y) \ge \max(b_x,b_y)$。即两个数都 $\ge \min(b_x,b_y)$，至少有一个数 $\ge \max(b_x,b_y)$。于是就可以首先把 $a_x,a_y$ 对 $\min(b_x,b_y)$ chkmax。

现在的限制就是 $a_x,a_y$ 至少有一个 $\ge \max(b_x,b_y)$。考虑最小割：我们尝试把每个点拆成 $p_{i,j}$。对于每个点，其与 $S$ 连通时，$a_i \ge j$。当加边 $(p_{i,v_1},p_{j,v_2},\infty)$ 时，则有限制：当 $a_i \ge v_1$ 时，$a_j \ge v_2$。整张图额外连接 $(p_{i,v_1},p_{i,v_1+1},p_{i,v_1}-a_{i0})$，即确立选择一个权值的代价。连接 $(p_{i,v_1+1},p_{i,v_1},+\infty)$ 以避免一条链上割两个点。

但是本题需要的约束可是 $a_i <v_1$ 时，$a_j \ge v_2$。方向是反的。

要解决这个问题，你需要有一个惊人的注意力：如果 $a_x \ge b_x$ 并且 $a_y \ge b_y$ 的话不用管。在调整过后，不会有 $a_x < b_x$ 且 $a_y < b_y$ 的情况。所以我们考虑的所有点对都形如 $a_x < b_x$ 且 $a_y \ge b_y$ 的情况。发现 $a_x$ 与 $b_x$ 的大小关系本身就能将所有数分成两个确定的集合，这不是二分图吗？

考虑把所有 $a_x < b_x$ 的点倒过来，即把 $p_{x,v}$ 看成是 $[a_x<v]$。则一个连边 $(p_{x,v_1},p_{y,v_2},+\infty)$ 则为如果 $a_x<v_1$，那么 $a_y \ge v_2$。非常契合限制。

跑一遍最小割即可。