luogu2219 [HAOI2007]修筑绿化带

和「理想的正方形」比较相似，需要先掌握那道题。

花坛外头每一边必须套上绿化带

#include <iostream>

#include <cstdio>

using namespace std;

int n, m, a, b, c, d, qwq[1005], twq, hwq, zzxz[1005][1005], ans;

int r[1005][1005], hzxz[1005][1005], cd[1005][1005], ab[1005][1005];

int main(){

	cin>>n>>m>>a>>b>>c>>d;

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

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

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

			r[i][j] += r[i-1][j] + r[i][j-1] - r[i-1][j-1];

		}

	for(int i=1; i<=n-c+1; i++)

		for(int j=1; j<=m-d+1; j++){

			int k=i+c-1;

			int l=j+d-1;

			cd[i][j] = r[k][l] - r[i-1][l] - r[k][j-1] + r[i-1][j-1];//计算所有c*d区域的和

		}

	for(int i=1; i<=n-a+1; i++)

		for(int j=1; j<=m-b+1; j++){

			int k=i+a-1;

			int l=j+b-1;

			ab[i][j] = r[k][l] - r[i-1][l] - r[k][j-1] + r[i-1][j-1];

		}

	a -= 2 + c - 1;//a*b的区域，是(a-2)*(b-2)的区域能放，然后再抛去c*d的大小带来的影响，就成了寻找一定区域内的最小值（因为要枚举a*b区域左上角，然后用单调队列迅速求出它所对应的(a-2)*(b-2)区域内的c*d区域的和的最小值），这样就方便了处理

	b -= 2 + d - 1;

	n -= c - 1;//这个矩阵就变成了所有c*d区域的和的矩阵

	m -= d - 1;

	for(int i=1; i<=n; i++){

		hwq = 1;

		twq = 0;

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

			int t=max(1, j-b+1);

			while(hwq<=twq && qwq[hwq]<=j-b)	hwq++;

			while(hwq<=twq && cd[i][qwq[twq]]>cd[i][j])	twq--;

			qwq[++twq] = j;

			hzxz[i][t] = cd[i][qwq[hwq]];

		}

	}

	for(int i=1; i<=m-b+1; i++){

		hwq = 1;

		twq = 0;

		for(int j=1; j<=n; j++){

			int t=max(1, j-a+1);

			while(hwq<=twq && qwq[hwq]<=j-a)	hwq++;

			while(hwq<=twq && hzxz[qwq[twq]][i]>hzxz[j][i])	twq--;

			qwq[++twq] = j;

			zzxz[t][i] = hzxz[qwq[hwq]][i];

		}

	}

	n += c - 1;

	m += d - 1;

	a += 2 + c - 1;

	b += 2 + d - 1;

	for(int i=1; i<=n-a+1; i++)

		for(int j=1; j<=m-b+1; j++)

			ans = max(ans, ab[i][j]-zzxz[i+1][j+1]);

	cout<<ans<<endl;

	return 0;

}