单调队列

把每列的最大值最小值预处理出来，压成一维用两个单调队列维护最大值最小值，和最左下表。

当队首元素相减不满足约束时出队，这个时候维护最小左下表，让它移动到两个队列中队首靠左的下表那继续更新答案。

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define FAST_IO ios::sync_with_stdio(false)using namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }template 
     
      inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 1000;int _, n, m, a[N][N], mx[N], mn[N], q1[N], q2[N], ans;int main(){    for(_ = read(); _; _ --){        ans = 0;        n = read(), m = read();        for(int i = 1; i <= n; i ++){            for(int j = 1; j <= n; j ++) a[i][j] = read();        }        for(int i = 1; i <= n; i ++){            for(int j = 1; j <= n; j ++){                mx[j] = 0, mn[j] = INF;            }            for(int t = i; t <= n; t ++){                for(int j = 1; j <= n; j ++){                    mx[j] = max(mx[j], a[t][j]);                    mn[j] = min(mn[j], a[t][j]);                }                int l1 = 1, r1 = 0, l2 = 1, r2 = 0, sgm = 1;                for(int j = 1; j <= n; j ++){                    while(l1 <= r1 && mx[q1[r1]] <= mx[j]) r1 --;                    q1[++r1] = j;                    while(l2 <= r2 && mn[q2[r2]] >= mn[j]) r2 --;                    q2[++r2] = j;                    while(l1 <= r1 && l2 <= r2 && mx[q1[l1]] - mn[q2[l2]] > m){                        if(q1[l1] == sgm) l1 ++;                        if(q2[l2] == sgm) l2 ++;                        sgm ++;                    }                    ans = max(ans, (j - sgm + 1) * (t - i + 1));                }            }        }        printf("%d\n", ans);    }    return 0;}