[题解] [HAOI2007] 修筑绿化带

题面

题解

题目意思比较简单, 就不在这里赘述了

本着练习平衡树的思路, 我把方法尝试往上面去套, 结果想不出

只能弃掉平衡树

最后想出来的方法是这样的

我们运用类似于高维前缀和那样一维一维加上去的方法

先横着统计在某个范围内和最小的 (c * d) 矩阵, 把贡献算在范围的右下角

注意, 这里保证了这个矩阵在以 ((i, j)) 为右下角的某个范围之内

然后再竖着计算答案, 我们固定 (a * b) 矩形的右边在某一列, 就只用考虑行的变化了

从上往下依次枚举右下角, 每次弹出不合法的, 然后跟合法的和的 (max) 做差取最大值

因为右下角储存的是一段以它为右下端点, 长度为 (b) , 高度为 (c) , 的范围内和最小的 (c * d) 矩阵

所以只要定了列, 它就不会超过列的影响范围, 也就是说, 列上面不会有冲突

所以只用看行之间的影响即可

这两步可以用单调队列实现

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 1005; 
using namespace std;

int n, m, a, b, c, d, w[N][N], sum[N][N], val[N][N], l, r, ans; 
struct node { int id, val; } q[N]; 

template < typename T >
inline T read()
{
	T x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * w; 
}

int getsum(int x1, int y1, int x2, int y2)
{
	return sum[x1][y1] - sum[x1][y2] - sum[x2][y1] + sum[x2][y2]; 
}

int main()
{
	n = read <int> (), m = read <int> (), a = read <int> (), b = read <int> (), c = read <int> (), d = read <int> ();
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			w[i][j] = sum[i][j] = read <int> ();
			sum[i][j] = sum[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; 
		}
	memset(val, 0x3f, sizeof(val)); 
	for(int tmp, i = c; i <= n; i++)
	{
		l = 1, r = 0; 
		for(int j = d; j <= n; j++)
		{
			tmp = getsum(i, j, i - c, j - d); 
			while(l <= r && q[r].val >= tmp)
				r--; 
			q[++r].val = tmp, q[r].id = j - d + 1;
			while(l <= r && q[l].id <= j - b + 2)
				l++; 
			val[i][j] = q[l].val; 
		}
	}
	for(int tmp, j = b - 1; j < m; j++)
	{
		l = 1, r = 0; 
		for(int i = c; i <= n; i++)
		{
			if(i - c + a - 1 <= n)
			{
				tmp = getsum(i - c + a - 1, j + 1, i - c - 1, j - b + 1); 
				while(l <= r && q[r].val <= tmp)
					r--; 
				q[++r].val = tmp, q[r].id = i - c + a - 1; 
			}
			while(l <= r && q[l].id <= i || q[l].id - a + 1 >= i - c + 1)
				l++; 
			ans = max(ans, q[l].val - val[i][j]); 
		}
	}
	printf("%d
", ans); 
	return 0; 
}