• POJ2823
• POJ1156
• HDU3041
• POJ3017

using namespace std;
int n,m,c,a[710][710],mn[710],mx[710];
int v1[710],v2[710];
int h1,h2,t1,t2;
void in1(int x)
{
    while(h1<=t1 && mn[v1[t1]]>mn[x]) t1--;
    v1[++t1]=x;
}
void in2(int x)
{
    while(h2<=t2 && mx[v2[t2]]<mx[x]) t2--;
    v2[++t2]=x;
}
int main()
{
    scanf("%d%d%d",&m,&n,&c);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)mn[j]=mx[j]=a[j][i];
        int u=min(i+99,m);
        for(int j=i+1;j<=u;j++)
        {
            for(int k=1;k<=n;k++)
            {
                mn[k]=min(mn[k],a[k][j]);
                mx[k]=max(mx[k],a[k][j]);
            }
            int w=j-i+1;
            h1=h2=1,t1=t2=0;
            int head=1,tail=1;
            while(tail<=n && (n-head+1)*w>ans)
            {
                in1(tail); in2(tail);
                while(head<=tail && h1<=t1 && h2<=t2 && mx[v2[h2]]-mn[v1[h1]]>c)
                {
                    head++;
                    while(h1<=t1 && v1[h1]<head) h1++;
                    while(h2<=t2 && v2[h2]<head) h2++;
                }
                ans=max(ans,w*(tail-head+1));
                tail++;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

练习：
POJ2823
POJ1156
HDU3041

POJ3017

<br />

<br />

#include<bits/stdc++.h>
using namespace std;
int n,m,c,a[710][710],mn[710],mx[710];
int v1[710],v2[710];
int h1,h2,t1,t2;
void in1(int x)
{
    while(h1<=t1 && mn[v1[t1]]>mn[x]) t1--;
    v1[++t1]=x;
}
void in2(int x)
{
    while(h2<=t2 && mx[v2[t2]]<mx[x]) t2--;
    v2[++t2]=x;
}
int main()
{
    scanf("%d%d%d",&m,&n,&c);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)mn[j]=mx[j]=a[j][i];
        int u=min(i+99,m);
        for(int j=i+1;j<=u;j++)
        {
            for(int k=1;k<=n;k++)
            {
                mn[k]=min(mn[k],a[k][j]);
                mx[k]=max(mx[k],a[k][j]);
            }
            int w=j-i+1;
            h1=h2=1,t1=t2=0;
            int head=1,tail=1;
            while(tail<=n && (n-head+1)*w>ans)
            {
                in1(tail); in2(tail);
                while(head<=tail && h1<=t1 && h2<=t2 && mx[v2[h2]]-mn[v1[h1]]>c)
                {
                    head++;
                    while(h1<=t1 && v1[h1]<head) h1++;
                    while(h2<=t2 && v2[h2]<head) h2++;
                }
                ans=max(ans,w*(tail-head+1));
                tail++;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

<br />

<br />