自动搬运

查看原文

来自洛谷，原作者为

	yedalong 注意力不够？刷题来凑！

搬运于2025-08-24 21:17:27，当前版本为作者最后更新于2025-02-26 19:28:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在写这道题之前请先学会二维前缀和。
本篇题解不会讲解任何有关前缀和的知识，不会请出门左转。

Solution

20pts

这是最简单的做法。对于每一次询问，暴力枚举右下角，接着再暴力求出这个区间内的和，时间复杂度 $O(Qn^2m^2)$。
由于过于简单，代码就不给了。

80pts

用上二维前缀和，对于每一次询问枚举右下角，$O(1)$ 直接求出区间内的和，取最大值即可。
时间复杂度 $O(Qnm)$。
参考代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
unordered_map<int,int> a[100005],qzh[100005],anss[100005];
int n,m,Q,x,y;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=m;j++)
			cin>>a[i][j];
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=m;j++)
			qzh[i][j]=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+a[i][j];
	cin>>Q;
	while(Q--){
		int ans=-1e18;
		cin>>x>>y;
		if(anss[x][y]){
			cout<<anss[x][y]<<'\n';
			continue;
		}
		for(int i = x;i<=n;i++){
			for(int j = y;j<=m;j++){
				ans=max(ans,qzh[i][j]-qzh[x-1][j]-qzh[i][y-1]+qzh[x-1][y-1]);
			}
		}
		cout<<ans<<'\n';
		anss[x][y]=ans;
	}
	return 0;
}
/*
这里的80分做法不太正经，因为用上了unordered_map，所以很浪费时间，加上一个记忆化才能卡到80。。。
建议使用vector来解决 
*/

100pts

考虑提前预处理好答案数组。
原本暴力预处理要四重循环，我们考虑只用三重循环来解决。
剩下的一重跑哪里去了？很简单，我们枚举的矩阵是宽为 $1$ 的不就好了？那要怎样操作呢？这样为什么是正确的呢？
先说一下是怎样枚举的。外面两重循环，一重是 $l$ 从 $1$ 到 $n$，另一重是 $r$ 从 $l$ 到 $n$，里面那一重是 $i$ 从 $m$ 到 $1$。
这是对于这样操作的一点解释：
这里有点像最大子段和。
当然，如果 $n$ 取到 $10^5$，$O(Q+n^2m)$ 的时间复杂度肯定是炸掉的。但是同理，如果 $n$ 太大我们可以选择 $m$，只是操作倒过来了而已。
时间复杂度 $O(Q+nm\sqrt{nm})$。可以通过此题。

AC code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,Q,x,y,last;
#define f(x,y,xx,yy) qzh[xx][yy]-qzh[xx][y-1]-qzh[x-1][yy]+qzh[x-1][y-1]
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	vector<int> a[n+5],qzh[n+5],ans[n+5];
	for(int i = 0;i<=n+1;i++) 
		for(int j = 0;j<=m+1;j++) 
			a[i].push_back(0),
			ans[i].push_back(-1e15),
			qzh[i].push_back(0);
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=m;j++)
			cin>>a[i][j];
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=m;j++)
			qzh[i][j]=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+a[i][j];
	if(n<=m)
		for(int l = 1;l<=n;l++)
			for(int r = l;r<=n;r++){
				last=0;
				for(int i = m;i>=1;i--)
					ans[l][i]=max(ans[l][i],f(l,i,r,i)+max(0ll,last)),last=f(l,i,r,i)+max(0ll,last);
			}
	else
		for(int l = 1;l<=m;l++)
			for(int r = l;r<=m;r++){
				last=0;
				for(int i = n;i>=1;i--)
					ans[i][l]=max(ans[i][l],f(i,l,i,r)+max(0ll,last)),last=f(i,l,i,r)+max(0ll,last);
			}
	cin>>Q;
	while(Q--)
		cin>>x>>y,
		cout<<ans[x][y]<<'\n';
	return 0;
}