看看 $N$,$M$，乘起来共有 $400w$ 个数，再看看答案的值域，$[0,10^9( \max - \min)]$。

好像可以二分答案并 $n^2$ 判断？

于是我们只需要再知道怎么判断分割是否可行。

其实，题目说的比较含蓄，整个地图划分的两个省其实都类似于旋转三角：

原因是这两条：

• 同省的任意两个小区块互相连接。
• 对于每一行/列，如果我们将这一行或列单独取出，这一行/列里同省的任意两个区块互相连接。这一行或列内的所有区块可以全部属于一个省。

所以判断就比较方便了。

我们可以先找出海拔的最小值 $AllMin$ 和最大值$AllMax$。

然后二分答案与海拔最小值的差（这样更好，我直接二分答案然后莫名被卡）

我们就要判断现在能否划分出两个类似于上图的三角，如果能就缩小答案，如果不能就增大答案。

那么让一块的最大值 $\le AllMin + x$，一块的最小值 $\ge AllMax - x$，依次判断上述四种情况是否有一种满足即可。

比如让红色省区的最大值 $\le AllMin + x$，以第二张图为例，只需要从第一行开始在每行中遍历。如果遍历到 第一个海拔 $\ge$ 最大值的地方 或者 超过上一行划分的红色省区右端的地方 就停（这一格不划入红色省区），转到下一行即可。否则将该格划入红色省区。

然后每行右边没划的地方自然全给蓝色省区，再判一下蓝色省区的最小值是否 $\ge AllMax - x$ 就行了。

其它情况类似。

时间复杂度 $O(H \times W \times \log( AllMax - AllMin) )$。

::::success[AC代码]

#include <cstdio>
#include <algorithm>
using namespace std;

int H, W, A[2020][2020];
int gmin, gmax;

bool check(int th)
{
    int sep = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (A[i][j] < gmax - th) {
                sep = max(sep, j + 1);
            }
        }
        for (int j = 0; j < W; ++j) {
            if (gmin + th < A[i][j]) {
                if (j < sep) return false;
            }
        }
    }
    return true;
}
void flip_row()
{
    for (int i = 0; i < H / 2; ++i) {
        for (int j = 0; j < W; ++j) {
            swap(A[i][j], A[H - 1 - i][j]);
        }
    }
}
void flip_col()
{
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W / 2; ++j) {
            swap(A[i][j], A[i][W - 1 - j]);
        }
    }
}
int solve()
{
    int lo = 0, hi = gmax - gmin;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (check(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}
int main()
{
    scanf("%d%d", &H, &W);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            scanf("%d", &(A[i][j]));
        }
    }

    gmin = gmax = A[0][0];
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            gmin = min(gmin, A[i][j]);
            gmax = max(gmax, A[i][j]);
        }
    }

        //翻转三次，得到四种情况
    int ret = solve();
    flip_row();
    ret = min(ret, solve());
    flip_col();
    ret = min(ret, solve());
    flip_row();
    ret = min(ret, solve());
    printf("%d\n", ret);
    return 0;
}

::::