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，但是已經開辟出來的元素值不變。