C++11(clang++ 3.9) 解法, 执行用时: 9553ms, 内存消耗: 92584K, 提交时间: 2020-02-01 13:06:09

#include <bits/stdc++.h>
 
constexpr int maxn = 2e3 + 5;

long long a[maxn][maxn],ans;
int n,m1,m2;

struct quad_tree
{
	long long sum[maxn*maxn*8];
	void build(int o,int x1,int y1,int x2,int y2)
	{
		if(x1>x2||y1>y2) return ;
		if(x1==x2&&y1==y2) {sum[o]=a[x1][y1];return ;}
		int mx=(x1+x2)>>1;
		int my=(y1+y2)>>1;
		build(4*o+1,x1,y1,mx,my);
		build(4*o+2,mx+1,y1,x2,my);
		build(4*o+3,x1,my+1,mx,y2);
		build(4*o+4,mx+1,my+1,x2,y2);
		sum[o]=std::max({sum[o],sum[4*o+1],sum[4*o+2],sum[4*o+3],sum[4*o+4]});
	}
	void query(int o,int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2)
	{
		if(x1>x2||y1>y2) return ;
    	if(x1>X2||x2<X1) return ;
    	if(y1>Y2||y2<Y1) return ;
    	if(sum[o]<=ans) return;
    	if(X1<=x1&&x2<=X2&&Y1<=y1&&y2<=Y2) {ans=std::max(ans,sum[o]);return ;}
    	int mx=(x1+x2)>>1;
    	int my=(y1+y2)>>1;
     	query(4*o+1,x1,y1,mx,my,X1,Y1,X2,Y2);
     	query(4*o+2,mx+1,y1,x2,my,X1,Y1,X2,Y2);
     	query(4*o+3,x1,my+1,mx,y2,X1,Y1,X2,Y2);
     	query(4*o+4,mx+1,my+1,x2,y2,X1,Y1,X2,Y2);
     	return ;
	}
}qt;

int main()
{
#ifdef LOCAL
	freopen("input.in","r",stdin);
#endif
	scanf("%d%d%d",&n,&m1,&m2);
	while(m1--)
	{
		int x1,x2,y1,y2,w;scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&w);
		a[x1][y1]+=w;
		a[x1][y2+1]-=w;
		a[x2+1][y1]-=w;
		a[x2+1][y2+1]+=w;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	qt.build(0,1,1,n,n);
	while(m2--)
	{
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2); ans=0;
		qt.query(0,1,1,n,n,x1,y1,x2,y2);
		printf("%lld\n",ans);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 9587ms, 内存消耗: 52840K, 提交时间: 2020-01-31 14:32:38

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
const int maxn = 2010;
const int maxm = 5e5+10;
ll a[maxn][maxn];
int n,m,cnt;
ll ans[maxm];
int Log[maxn];
ll RMQ[maxn][30]; 
void init(int x)
{
	Log[0] = -1;
	for (int i = 1; i <= n; i++) Log[i] = Log[i >> 1] + 1;
	for (int i = 1; i <= n; i++) RMQ[i][0] = a[x][i];
	for (int j = 1; j <= 13; j++)
		for (int i = 1; i + (1 << j) - 1 <=n; i++)
			RMQ[i][j] = max(RMQ[i][j - 1], RMQ[i + (1 << j - 1)][j - 1]);
}
ll Max(int l, int r)
{
	int k = Log[r - l + 1];
	return max(RMQ[l][k], RMQ[r - (1 << k) + 1][k]);
}
void prework()
{
	int x1,y1,x2,y2; ll w;
	while(m--)
	{
		scanf("%d%d%d%d%lld",&x1,&y1,&x2,&y2,&w);
		a[x1][y1]+=w;
		a[x2+1][y1]+=-w;
		a[x1][y2+1]+=-w;
		a[x2+1][y2+1]+=w;
	}
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	       a[i][j]+=a[i][j-1];
	for(int j=1;j<=n;j++)
	    for(int i=1;i<=n;i++)
	       a[i][j]+=a[i-1][j];
} 
struct Node
{
	int x1,y1,x2,y2,id;
	Node()
	{
		
	}
	Node(int _x1,int _y1,int _x2,int _y2,int _id)
	{
		x1=_x1,y1=_y1,x2=_x2,y2=_y2,id=_id;
	}
}node[maxm];
int main()
{
	scanf("%d%d%d",&n,&m,&cnt);
	prework();
	for(int i=1;i<=cnt;i++) scanf("%d%d%d%d",&node[i].x1,&node[i].y1,&node[i].x2,&node[i].y2),node[i].id=i;
	for(int i=1;i<=n;i++)
	{
		init(i);
		for(int j=1;j<=cnt;j++)
		{
			if(node[j].x1<=i&&i<=node[j].x2)
			ans[j]=max(ans[j],Max(node[j].y1,node[j].y2));
		}
	}
	for(int i=1;i<=cnt;i++) printf("%lld\n",ans[i]);
	return 0;
}