写一半停电了...gg
本来是想做考题用的。想想算了。似乎太简单了。

Problem

自行原 OJ(Luogu)查看。

错了很久的题。从 2 号之前开始做做到现在（2 月 8 号）。

题意不概述。大体思想：枚举 ab 矩形的左上角 $(i,j)$ ，则要查找的范围是 $(i+1,j+1)$ 到 $(i+a-2,j+b-2)$ ，找到 cd 矩形数字之和的最小就 OK 了。
则我们先用前缀和将 cd 矩形用左上角代替，缩小原矩阵。
然后找矩阵最小值即可。做法同 完美的正方形 一题。

为什么错到现在呢？
单调队列出入完更新一次之后，要取队头元素，我取的队尾...

Code

// Code by ajcxsu
// Problem: P2219

#include<bits/stdc++.h>
using namespace std;

const int N=1001;
int mz[N][N]; // 初始矩阵
int S[N][N]; // 二维前缀和
inline int gs(int x1,int y1,int x2,int y2) {
    return S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1];
}
int m2[N][N]; // 第二次处理
int m3[N][N]; // 第三次处理
int m4[N][N]; // 第四次处理

void putout(int arr[][N],int x,int y) {
    cout<<x<<' '<<y<<endl;
    for(int i=1;i<=x;i++) {
        for(int j=1;j<=y;j++) cout<<arr[i][j]<<' ';
        cout<<endl;
    }
} // DEBUG


int main() {
    ios::sync_with_stdio(false);
    int n,m,a,b,c,d;
    cin>>n>>m>>a>>b>>c>>d;
    /* 读入矩阵 */
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mz[i][j];
    /* 处理前缀和 */
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            S[i][j]=S[i][j-1]+mz[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            S[i][j]+=S[i-1][j];
    /* 第二次处理,缩矩阵 */
    for(int i=1;i+c-1<=n;i++)
    for(int j=1;j+d-1<=m;j++)
        m2[i][j]=gs(i,j,i+c-1,j+d-1);
    n=n-c+1;
    m=m-d+1;
    /* 第三次处理,开始计算最小值,计算矩阵大小,再缩矩阵列 */
    int e=a-2-c+1,f=b-2-d+1; // 行,列
    int qu[N],pos[N],h,t;
    for(int j=1;j<=m;j++){
        h=t=0;
        for(int i=1;i<=n;i++) {
            while(h!=t && pos[h]<i-e+1) h++;
            while(h!=t && qu[t-1]>=m2[i][j]) t--;
            qu[t]=m2[i][j]; pos[t++]=i;
            if(i-e+1>0) m3[i-e+1][j]=qu[h];
        }
    }
    n=n-e+1;
    /* 第四次处理,计算行最小值,进而计算最大差 */
    int ans=-0x3f3f3f3f;
    for(int i=2;i<=n-1;i++) {
        h=t=0;
        for(int j=2;j<=m+d-2;j++) {
            while(h!=t && pos[h]<j-f+1) h++;
            while(h!=t && qu[t-1]>=m3[i][j]) t--;
            qu[t]=m3[i][j]; pos[t++]=j;
            if(j-f>=1) ans=max(ans,gs(i-1,j-f,i-2+a,j-f+b-1)-qu[h]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol_luogu_2219.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆