解析待写
例题：2020 CCPC Wannafly Winter Camp Day5 I 题
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3+10;
int n, m1, m2;
int x, y, xl, xr, yl, yr;
ll w;
ll a[N][N];
void add(){
a[xl][yl] += w;
a[xl][yr+1] -= w;
a[xr+1][yl] -= w;
a[xr+1][yr+1] += w;
}
ll tree[4*N][4*N];
void up_y(int ox, int oy, int l, int r, int f){
if(l == r){
if(f) tree[ox][oy] = w;
else tree[ox][oy] = max(tree[ox<<1][oy], tree[ox<<1|1][oy]);
return ;
}
int mid = l+r >> 1;
if(y <= mid) up_y(ox, oy<<1, l, mid, f);
else up_y(ox, oy<<1|1, mid+1, r, f);
tree[ox][oy] = max(tree[ox][oy<<1], tree[ox][oy<<1|1]);
}
void up_x(int ox, int l, int r){
if(l == r){
up_y(ox, 1, 1, n, 1);
return ;
}
int mid = l+r >> 1;
if(x <= mid) up_x(ox<<1, l, mid);
else up_x(ox<<1|1, mid+1, r);
up_y(ox, 1, 1, n, 0);
}
ll qu_y(int ox, int oy, int l, int r){
if(l >= yl && r <= yr){
return tree[ox][oy];
}
int mid = l+r >> 1;
ll res = 0;
if(yl <= mid) res = max(res, qu_y(ox, oy<<1, l, mid));
if(yr > mid) res = max(res, qu_y(ox, oy<<1|1, mid+1, r));
return res;
}
ll qu_x(int ox, int l, int r){
if(l >= xl && r <= xr) {
return qu_y(ox, 1, 1, n);
}
int mid = l+r >> 1;
ll res = 0;
if(xl <= mid) res = max(res, qu_x(ox<<1, l, mid));
if(xr > mid) res = max(res, qu_x(ox<<1|1, mid+1, r));
return res;
}
int main(){
scanf("%d%d%d", &n, &m1, &m2);
while(m1--){
scanf("%d%d%d%d%lld", &xl, &yl, &xr, &yr, &w);
add();
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
a[i][j] += a[i][j-1] + a[i-1][j] - a[i-1][j-1];
x = i, y = j, w = a[i][j];
up_x(1, 1, n);
}
}
while(m2--){
scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
ll ans = qu_x(1, 1, n);
printf("%lld\n", ans);
}
return 0;
}