注意到这道题本质就是一个矩形求和矩形赋值的操作。其中满足：对于任意一个点，每次赋予的权值是单调递增的。
这看起但就像是一个二维线段树能做的范畴。但是众所周知，二维线段树的外层无法进行标记上传操作（无法 pushup），故而这题我们考虑标记永久化。同时，为了简化问题，我们先关心一维的情况。
我们考虑对于每个点，记录两个权值：\(mx\) 和 \(tg\)。前者为当前区间的最大值，后者为标记值。
- 对于修改操作。沿用常规的懒标记线段树的方法，更新那些被当前区间完全包含的极大区间的 \(tg\) 值。同时，更新修改过程中遍历到过的所有节点的 \(mx\)。
- 对于询问操作，进行标记永久化的查询。同时，对于那些被当前区间完全包含的极大区间，我们也拿它的 \(mx\) 值区更新答案。
二维情况类似。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
int D, S, N;
namespace T{
struct SGTx{
int mx[2050], tg[2050];
void Upd(int p, int l, int r, int x, int y, int v){
mx[p] = max(mx[p], v);
if(x <= l && r <= y){tg[p] = max(tg[p], v); return;}
int mid = l + r >> 1;
if(x <= mid) Upd(p << 1, l, mid, x, y, v);
if(mid < y) Upd(p << 1 | 1, mid + 1, r, x, y, v);
}
int Qry(int p, int l, int r, int x, int y){
if(x <= l && r <= y) return mx[p];
int mid = l + r >> 1, ret = tg[p];
if(x <= mid) ret = max(ret, Qry(p << 1, l, mid, x, y));
if(mid < y) ret = max(ret, Qry(p << 1 | 1, mid + 1, r, x, y));
return ret;
}
} mx[2050], tg[2050];
void Upd(int p, int l, int r, int x1, int y1, int x2, int y2, int v){
mx[p].Upd(1, 1, S, x2, y2, v);
if(x1 <= l && r <= y1){tg[p].Upd(1, 1, S, x2, y2, v); return;}
int mid = l + r >> 1;
if(x1 <= mid) Upd(p << 1, l, mid, x1, y1, x2, y2, v);
if(mid < y1) Upd(p << 1 | 1, mid + 1, r, x1, y1, x2, y2, v);
}
int Qry(int p, int l, int r, int x1, int y1, int x2, int y2){
if(x1 <= l && r <= y1) return mx[p].Qry(1, 1, S, x2, y2);
int mid = l + r >> 1, ret = tg[p].Qry(1, 1, S, x2, y2);
if(x1 <= mid) ret = max(ret, Qry(p << 1, l, mid, x1, y1, x2, y2));
if(mid < y1) ret = max(ret, Qry(p << 1 | 1, mid + 1, r, x1, y1, x2, y2));
return ret;
}
}
int main(){
scanf("%d%d%d", &D, &S, &N), D++, S++;
FL(i, 1, N){
int d, s, w, x, y, h;
scanf("%d%d%d%d%d", &d, &s, &w, &x, &y), x++, y++;
h = T::Qry(1, 1, D, x, x + d - 1, y, y + s - 1);
T::Upd(1, 1, D, x, x + d - 1, y, y + s - 1, h + w);
}
printf("%d\n", T::Qry(1, 1, D, 1, D, 1, S));
return 0;
}