郊游

（1 s ，128 MB, trip .cpp/c/pas ）

【问题描述】

小朋友们出去郊游，明明和亮亮负责在草地上开一个篝火晚会。这个草地你可以认为是由
N * M 块单位长度为 1 的小正方形的草组成。
显然有的地方草长的好，有的地方长的不好，坐在上面显然舒服度是不一样的，于是每一
块草都有一个舒服度 F。
现在明明和亮亮要选定一个 a*b 的草场作为晚会的地点，小朋友们就坐在上面，显然他希
望小朋友们坐的最舒服！
不过别急，篝火晚会怎么能少了篝火呢，篝火需要占用 c*d 的草地，当然，篝火必须严格
放置在选定的草地的内部，也就是说，篝火的边界不能和选定操场的边界有公共部分，不然学
生们怎么围着篝火开晚会呢？
给定 N*M 大草地每一块的舒服度，寻找一个 a*b 的草地，除去一个严格内部的 c*d 的
子草地，使得总的舒服度最大。

【输入描述】

第 1 行：6 个整数，M, N, b, a, d, c
第 2~N+1 行：每行 M 个整数，第 i 行 j 列的整数 Fi,j 表示，第 i 行 j 列的单位草
地的舒服度。

【输出描述】

一个整数，表示最大的舒服值。

【样例输入】

8 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2

【样例输出】

【样例说明】

下面的图片就是对样例的解释，阴影区域就是最佳的选择方案。

比如方案 4 1 4 1 就是显然非法的，因为篝火出现出现在了选定草地的边界，学生们无
法严格围住篝火。

【数据规模】

1 ≤ Fi,j ≤ 100
3 ≤ a ≤ N
3 ≤ b ≤ M
1 ≤ c ≤ a-2
1 ≤ d ≤ b-2
对于 40% 的数据 N,M ≤ 10
对于 60% 的数据 N,M ≤ 150
对于 100% 的数据 N,M ≤ 1000

所用知识

前缀和，ST表，滑动窗口（单调队列）

c++代码

#include<bits/stdc++.h>
using namespace std;
int m,n,a,b,c,d;
int MAP;
int tot[1005][1005];
int gh[1005][1005];
int st[1005][1005][15];
int log_2[1005];
int ANS;
deque< int > v;
deque< int > y;
int main()
{
	freopen("trip.in","r",stdin);
	freopen("trip.out","w",stdout);
	for(int i=1,ans=0;i<=1005;i++)//预处理 LOG2
	{
		if(i>=(1<<ans))
			ans++;
		log_2[i]=ans-1;
	}
	cin>>n>>m>>b>>a>>d>>c;
	for(int i=1;i<=m;i++)
	{
		int all=0;
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&MAP);
			all+=MAP;
			tot[i][j]=tot[i-1][j]+all;//前缀和 
		}
	}
	for(int i=1;i<=m-c+1;i++)//   st表 
		for(int j=1;j<=n-d+1;j++)
			st[i][j][0]=tot[i+c-1][j+d-1]-tot[i-1][j+d-1]-tot[i+c-1][j-1]+tot[i-1][j-1];
	for(int x=1;x<=10;x++)//  st表初始化 
		for(int i=1;i<=m&&i+(1<<(x-1))<=n;i++)
			for(int j=1;j<=n;j++)
				st[i][j][x]=min(st[i][j][x-1],st[i+(1<<(x-1))][j][x-1]);
	for(int i=1;i<=m-c+1;i++)
		for(int j=1;j<=n-d+1;j++)
			gh[i][j]=min(st[i][j][log_2[a-1-c]],st[i+a-1-c-(1<<log_2[a-1-c])][j][log_2[a-1-c]]);
	for(int i=1;i<=m-a+1;i++)// 滑动窗口 
	{
		while(v.size())
		{
			v.pop_back();
			y.pop_back();
		}
		for(int j=2;j<b-d;j++)
		{
			while(v.size()&&gh[i+1][j]<=v.back())
			{
				v.pop_back();
				y.pop_back();
			}
			v.push_back(gh[i+1][j]);
			y.push_back(j);
		}
		for(int j=1;j<=n-b+1;j++)
		{
			int he=tot[i+a-1][j+b-1]-tot[i-1][j+b-1]-tot[i+a-1][j-1]+tot[i-1][j-1];
			int now=gh[i+1][j+b-d-1];
			while(v.size()&&now<=v.back())
			{
				v.pop_back();
				y.pop_back();
			}
			v.push_back(now);
			y.push_back(j+b-d-1);
			while(y.front()<=j)
			{
				v.pop_front();
				y.pop_front();
			}
			ANS=max(ANS,he-v.front());
		}
	}
	cout<<ANS<<endl;
	return 0;
}