CF1606D Red-Blue Matrix

​​传送门​​

题意：给一个\(n*m\)的矩阵，让你把一些行涂成红色，剩下的涂成蓝色，但不能都涂红或蓝。问在这个基础上，能否从某一列将矩阵分成两半，使左半矩阵的红色部分的每一个数都大于蓝色部分的每一个数，而右半矩阵的蓝色部分的每一个数都大于红色部分的每一个数。（\(2 \leqslant n,m \leqslant 5 \times 10^5,n \cdot m \leqslant 10^6\)）

这题看起来贼吓人，比赛的时候做出来的人竟然还没e题多。我承认我也被吓着了，想了一个很复杂，而且也不好实现的图论相关的算法。

实际上这题很暴力的。最为关键的一点在于，先把每一行按首元素从小到大排序。这样一定是前几行涂成蓝色，后几行涂成红色（否则第一个元素就不满足要求）。然后我们枚举分割矩阵的那一列\(k\)，再枚举涂成蓝色的行数\(x\)，那么只要判断左半矩阵前\(x\)行的最大值是否小于后\(n - x\)行的最小值，以及右半矩阵前\(x\)行的最小值是否大于后\(n-x\)行的最大值。而这些，可以在\(o(nm)\)下预处理出从四个角向中间延伸的二维前（后）缀最大（小）值。

因此时间复杂度是\(o(n\log n+nm)\)的。

debug的时候才知道，vector的​<code>​resize(n, x)​</code>​是把新开辟出来的空间的初始赋值成x，但是已经开辟出来的元素值不变。