题意描述

JOIOI 王国是一个 $H$ 行 $W$ 列的长方形网格，每个 $1 \times 1$ 的子网格都是一个正方形的小区块。为了提高管理效率，我们决定把整个国家划分成两个省 JOI 和 IOI。

我们定义，两个同省的区块互相连接，意为从一个区块出发，不用穿过任何一个不同省的区块，就可以移动到另一个区块。有公共边的区块间可以任意移动。

我们不希望划分得过于复杂，因此划分方案需满足以下条件：

  • 区块不能被分割为两半，一半属 JOI 省，一半属 IOI 省。
  • 每个省必须包含至少一个区块，每个区块也必须属于且只属于其中一个省。
  • 同省的任意两个小区块互相连接。对于每一行/列，如果我们将这一行/列单独取出，这一行/列里同省的任意两个区块互相连接。这一行/列内的所有区块可以全部属于一个省。

现给出所有区块的海拔，第 $i$ 行第 $j$ 列的区块的海拔为 $A_{i,j}$。

设 JOI 省内各区块海拔的极差（最大值减去最小值）为 $ R{JOI} $ ，IOI 省内各区块海拔的极差为 $ R{IOI} $。

在划分后，省内的交流有望更加活跃。但如果两个区块的海拔差太大，两地间的交通会很不方便。 因此，理想的划分方案是 $max(R{JOI},R{IOI})$ 尽可能小。而你的任务是求出这个最小值。

输入格式

第一行，两个整数 $H,W$ ，用空格分隔。

在接下来的 $H$ 行中，第 $i$ 行有 $W$ 个整数 $A{i,1},A{i,2}, \cdots ,A_{i,W}$ ，用空格分隔。

输入的所有数的含义见题目描述。

输出格式

一行，一个整数，表示 $max(R{JOI},R{IOI})$ 可能的最小值。

Input & Output ‘s examples

Input ‘s eg

4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10

Output ‘s eg

11

数据范围和约定

对于 $15\%$ 的数据， $H,W \leqslant 10$。

对于另外 $45\%$ 的数据， $H,W \leqslant 200$。

对于所有数据， $2 \leqslant H,W \leqslant 2000,A_{i,j} \leqslant 10^9 , 1 \leqslant i \leqslant H,1 \leqslant j \leqslant W$。

分析

题目中提到最大值最小，明示二分答案。

考虑怎么书写 $\text{check}$ 函数？重新读一下题，不难发现能推出以下几条特性：

  1. 划分的边界一定是阶梯状的。
  2. 一个区域中包含的点越少，其可能的极差越小。
  3. 整个矩阵的最大值 & 最小值一定在分别两个区域中。

其中性质 $2$ 的感性理解是考虑在一个区域中加一个点，其极差可能不变或变大，故点数越少其可能的极差越小。

故二分极差 $x$ ，且强行钦定最大值在区间 $\text{A}$ 中，这样就可以得到区间 $\text{A}$ 能取的最小值。接着把不会影响到极差的值全部加入到区间 $\text{A}$，以方便之后对剩下区间进行处理。

根据性质 $3$，剩下的区域一定有区间最小值。设其为区间 $\text{B}$，则我们可以根据二分出的极差求区间 $\text{B}$ 能取的最大值。之后暴力扫一遍区域 $\text{B}$ 中有没有比这个最大值大的元素即可。

还有一个细节就是阶梯状的边界可能是从左下到右上，右下到左上，右上到左下，左上到右下四种情况，分开 $\text{check}$ 的话比较麻烦，故可以在 $\text{check}$ 出一种情况之后翻转 $90°$ 再次 $\text{check}$，在四种情况中取最优的。

时间复杂度 $O(n^2 \log n)$。足以通过本题

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 100000 + 5;
const int HA = 998244353;

int n , m;
ll s[2005][2005];
ll maxn = -0x3f3f3f3f , minn = 0x3f3f3f3f;


bool check(int x) {
    int poi = m + 1;
    rep(i , 1 , n) {
        int t = 0;
        rep(j , 1 , min(poi , m)) {
            if(maxn - s[i][j] <= x) t = max(t , j);
            else break;
        }
        poi = t;
        rep(j , t + 1 , m) {
            if(s[i][j] - minn > x) return 0;
        }
    }
    return 1;
}

ll solve() {
    ll l = 0 , r = maxn - minn;
    while(l + 1 < r) {
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    if(check(l)) return l;
    else return r;
}

void TrunR() {
    rep(i , 1 , n) {
        rep(j , 1 , m / 2) {
            swap(s[i][j] , s[i][m - j + 1]);
        }
    }
}

void TrunL() {
    rep(i , 1 , n / 2) {
        rep(j , 1 , m) {
            swap(s[i][j] , s[n - i + 1][j]);
        }
    }
}

#define LOCAL

int main() {
    #ifdef LOCAL
        freopen("joioi.in" , "r" , stdin);
        freopen("joioi.out" , "w" , stdout);
    #endif
    read(n) , read(m);
    rep(i , 1 , n) {
        rep(j , 1 , m) {
            read(s[i][j]);
            maxn = max(maxn , s[i][j]);
            minn = min(minn , s[i][j]);
        }
    }
    ll ans = 0x3f3f3f3f;
    ans = min(ans , solve()) , TrunR();
    ans = min(ans , solve()) , TrunL();
    ans = min(ans , solve()) , TrunR();
    ans = min(ans , solve());
    printf("%lld\n" , ans);

    return 0;
}

THE END