宁夏网站建设中百度云搜索引擎

这是一道二维线段树（树套树）+标记永久化的模版题

前置知识点（来自董晓算法）

好，现在开始我们的分析：

题意简述：

在一个二维平面内，有给定的坐标，在这个坐标范围内加上这个物品的厚度。最后输出不超过极限的最高坐标。

解法分析：

由于看到了区间修改，所以第一时间想到了线段树。（好像树状数组也可以做，只是本人不会）但是，要注意到这是一个二维线区间修改，所以要引入一种新的东西：二维线段树（什么！你还没有点开前置知识点？！快去看看！）

因为有董晓老师对于二维线段树的详细讲解了，我在这里就不过多赘述。

发现问题：

对于内层而言，传统的做法可以胜任，可以打 lazy 标记，pushdown 和 pushup 也都是可以进行的。但是对于外层而言，信息量太大，无法进行，所以需要使用一种新办法：标记永久化。

知识点，标记永久化

好了，问题到这就已经解决了，直接上代码吧。（四十几行真的不长了QAQ）

#include<iostream>
#include<cstring>
#include<algorithm>
#define ls(x) x*2
#define rs(x) x*2+1
#define mid l+(r-l)/2
using namespace std;
const int MAXN=4e3+10;
int d,s,n;
int a,b,h,x,y;
struct segy{int mx[MAXN],tag[MAXN];void change(int u,int l,int r,int y1,int y2,int h){mx[u]=max(mx[u],h);if(y1<=l&&r<=y2){tag[u]=max(tag[u],h);return ;}if(y1<=mid)change(ls(u),l,mid,y1,y2,h);if(y2>mid)change(rs(u),mid+1,r,y1,y2,h);}int query(int u,int l,int r,int y1,int y2){if(y1<=l&&r<=y2)return mx[u];int ans=tag[u];if(y1<=mid)ans=max(ans,query(ls(u),l,mid,y1,y2));if(y2>mid)ans=max(ans,query(rs(u),mid+1,r,y1,y2));return ans;}
}mx[MAXN],tag[MAXN];
void change(int u,int l,int r,int x1,int x2,int y1,int y2,int h){mx[u].change(1,1,s,y1,y2,h);if(x1<=l&&r<=x2){tag[u].change(1,1,s,y1,y2,h);return ;}if(x1<=mid)change(ls(u),l,mid,x1,x2,y1,y2,h);if(x2>mid)change(rs(u),mid+1,r,x1,x2,y1,y2,h);
}
int query(int u,int l,int r,int x1,int x2,int y1,int y2){if(x1<=l&&r<=x2)return mx[u].query(1,1,s,y1,y2);int ans=tag[u].query(1,1,s,y1,y2);if(x1<=mid)ans=max(ans,query(ls(u),l,mid,x1,x2,y1,y2));if(x2>mid)ans=max(ans,query(rs(u),mid+1,r,x1,x2,y1,y2));return ans;
}
int main(){cin>>d>>s>>n;for(int i=1;i<=n;i++){cin>>a>>b>>h>>x>>y;x++;y++;h+=query(1,1,d,x,x+a-1,y,y+b-1);change(1,1,d,x,x+a-1,y,y+b-1,h);}cout<<mx[1].mx[1]<<"\n";return 0;
}