Main idea: Find the maximum matrix so that the difference between the maximum and the minimum does not exceed m.

Topic train of thought:

Enumerate the upper and lower boundaries of the matrix, and maintain the disassembly range by monotonous queues.

How to maintain it? We initialize every position of this line every time we enumerate the lower boundaries, the maximum and minimum values of this column for each location, and then how to know if it is the solution. We maintain a descending order in the maximum monotonic queue, so the head of the queue must be the largest current edge. It is bigger than this, and the minimum monotonous queue maintains an incremental order, the head of the queue is the smallest, and there is no smaller front than this, so when we choose a right boundary, the farther the left boundary is, the better, so we directly take the head of the queue, then the difference between the maximum and minimum may be larger than m after taking out the head of the queue.

Since it's bigger than m, we must jump back together, but where do we jump to the head of two teams? The answer is that the head of two queues + 1 is on the left. Why is it on the left? Because there's no bigger head in front than the head of the team, so when the head of the minimum team is more on the left than this, it's optional. The minimum queue is the same. There is no earlier one in front of the head of the team, so even the maximum head of the team is no problem in front, so take both minutes.

The idea of this question is still very wild. It's hard to think about it.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 505;
int Max[MAXN],Min[MAXN];
int a[MAXN][MAXN];
int q1[MAXN],q2[MAXN];
int main()
{
    int n,m;
 
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
            //for(int j=1;j<=n;j++){
            //    Max[j]=Min[j]=a[i][j];
            //}
            memset(Max,0,sizeof(Max));
            memset(Min,0x3f,sizeof(Min));
            for(int j=i;j<=n;j++){
                for(int k=1;k<=n;k++){
                    Max[k]=max(Max[k],a[j][k]);
                    Min[k]=min(Min[k],a[j][k]);
                }
                int l1=0,l2=0,r1=-1,r2=-1;
                int now=1;
                for(int k=1;k<=n;k++){
                    while(l1<=r1&& Max[ q1[r1] ] <= Max[ k ])r1--;
                    q1[++r1]=k;
                    while(l2<=r2&& Min[ q2[r2] ] >= Min[ k ])r2--;
                    q2[++r2]=k;
                    while(l1<=r1 && l2<=r2 && Min[q2[l2]]+m<Max[q1[l1]]){
                        now=min(q2[l2]+1,q1[l1]+1);
                        while(l1<=r1 && q1[l1]<now)l1++;
                        while(l2<=r2 && q2[l2]<now)l2++;
 
                    }//cout<<j-i+1<<" * "<<k-now+1<<" +++ "<<ans<<endl;
                    ans=max(ans,(j-i+1)*(k-now+1));
 
                }
            }
        }
        printf("%d\n",ans);
    }
}