P2219 [HAOI2007]修筑绿化带（单调队列）

时间：2023-03-08 18:36:09

P2219 [HAOI2007]修筑绿化带

二维单调队列

写了这题 P2216 [HAOI2007]理想的正方形  后，你发现可以搞个二维单调队列

来保存矩形（i+1,i+A-1）（j+1,j+B-1）内矩形C*D的最小值

具体怎么搞呢

先搞出二维前缀和

蓝后先按$x$轴跑一遍单调队列，再按$y$轴跑一遍就好辣

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

inline int Max(int a,int b){return a>b?a:b;}

#define N 1005

int n,m,A,B,C,D,s[N][N],h[N],L,R,ans;

int w1[N][N],w2[N][N],a1[N][N],a2[N][N];

int main(){

    scanf("%d%d%d%d%d%d",&n,&m,&A,&B,&C,&D);

    register int i,j;

    for(i=;i<=n;++i)

        for(j=;j<=m;++j){

            scanf("%d",&s[i][j]);

            s[i][j]+=s[i-][j]+s[i][j-]-s[i-][j-];

        }//前缀和

    for(i=A;i<=n;++i)

        for(j=B;j<=m;++j)

            w1[i][j]=s[i][j]-s[i-A][j]-s[i][j-B]+s[i-A][j-B];//A*B矩阵的和

    for(i=C+;i<n;++i)

        for(j=D+;j<m;++j)

            w2[i][j]=s[i][j]-s[i-C][j]-s[i][j-D]+s[i-C][j-D];//C*D矩阵的和

    for(i=C+;i<n;++i){

        L=,R=;

        for(j=D+;j<m;++j){

            while(L<=R&&h[L]<j-B++D) ++L;

            while(L<=R&&w2[i][h[R]]>=w2[i][j]) --R;

            h[++R]=j;

            a1[i][j]=w2[i][h[L]];

        }

    }//先处理出x轴上的最小值

    for(j=D+;j<m;++j){

        L=,R=;

        for(i=C+;i<n;++i){

            while(L<=R&&h[L]<i-A++C) ++L;

            while(L<=R&&a1[h[R]][j]>=a1[i][j]) --R;

            h[++R]=i;

            a2[i][j]=a1[h[L]][j];

        }

    }//再按y轴跑一遍单调队列

    for(i=A;i<=n;++i)

        for(j=B;j<=m;++j)

            ans=Max(ans,w1[i][j]-a2[i-][j-]);//取最小的C*D矩阵的值

    printf("%d",ans);

    return ;

}

相关文章