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

传送门

需要n*m的算法，考虑单调队列

可以预处理出来

a[i][j]表示以i,j为右下角的绿化带+花坛的和

b[i][j]表示以i,j为右下角的花坛的和

那么我们可以单调队列跑出来在A-C-1,B-D-1的矩阵中的b[i][j]的最小值

枚举i,j，用取a[i][j]-ans[i-1][j-1]的最大值

#include <cstdio>

#include <iostream>

#define N 2001

using namespace std;

int n, m, A, B, C, D, E, F, h, t, ans;

int a[N][N], b[N][N], c[N][N], ans1[N][N], ans2[N][N], q[N];

inline int read()

{

	int x = 0, f = 1;

	char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

	return x * f;

}

inline void work1(int k)

{

	int i;

	h = 1, t = 0;

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

	{

		while(h <= t && b[k][q[t]] > b[k][i]) t--;

		q[++t] = i;

		while(h <= t && q[h] <= i - F) h++;

		ans1[k][i] = b[k][q[h]];

	}

}

inline void work2(int k)

{

	int i;

	h = 1, t = 0;

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

	{

		while(h <= t && ans1[q[t]][k] > ans1[i][k]) t--;

		q[++t] = i;

		while(h <= t && q[h] <= i - E) h++;

		ans2[i][k] = ans1[q[h]][k];

	}

}

int main()

{

	int i, j;

	n = read();

	m = read();

	A = read();

	B = read();

	C = read();

	D = read();

	E = A - C - 1;

	F = B - D - 1;

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

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

			c[i][j] = read() + c[i][j - 1] + c[i - 1][j] - c[i - 1][j - 1];

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

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

		{

			if(i >= A && j >= B) a[i][j] = c[i][j] - c[i - A][j] - c[i][j - B] + c[i - A][j - B];

			if(i >= C && j >= D) b[i][j] = c[i][j] - c[i - C][j] - c[i][j - D] + c[i - C][j - D];

		}

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

	for(i = D; i <= m; i++) work2(i);

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

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

			ans = max(ans, a[i][j] - ans2[i - 1][j - 1]);

	printf("%d\n", ans);

	return 0;

}