嘉兴的网站设计公司有哪些,wordpress themes.php,电脑大型网络游戏排行,秒收录的网站这是一道二维线段树#xff08;树套树#xff09;标记永久化的模版题
前置知识点#xff08;来自董晓算法#xff09;
好#xff0c;现在开始我们的分析#xff1a;
题意简述#xff1a;
在一个二维平面内#xff0c;有给定的坐标#xff0c;在这个坐标范围内加上…这是一道二维线段树树套树标记永久化的模版题
前置知识点来自董晓算法
好现在开始我们的分析
题意简述
在一个二维平面内有给定的坐标在这个坐标范围内加上这个物品的厚度。最后输出不超过极限的最高坐标。
解法分析
由于看到了区间修改所以第一时间想到了线段树。好像树状数组也可以做只是本人不会但是要注意到这是一个二维线区间修改所以要引入一种新的东西二维线段树什么你还没有点开前置知识点快去看看
因为有董晓老师对于二维线段树的详细讲解了我在这里就不过多赘述。
发现问题
对于内层而言传统的做法可以胜任可以打 lazy 标记pushdown 和 pushup 也都是可以进行的。但是对于外层而言信息量太大无法进行所以需要使用一种新办法标记永久化。
知识点标记永久化
好了问题到这就已经解决了直接上代码吧。四十几行真的不长了QAQ
#includeiostream
#includecstring
#includealgorithm
#define ls(x) x*2
#define rs(x) x*21
#define mid l(r-l)/2
using namespace std;
const int MAXN4e310;
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(y1lry2){tag[u]max(tag[u],h);return ;}if(y1mid)change(ls(u),l,mid,y1,y2,h);if(y2mid)change(rs(u),mid1,r,y1,y2,h);}int query(int u,int l,int r,int y1,int y2){if(y1lry2)return mx[u];int anstag[u];if(y1mid)ansmax(ans,query(ls(u),l,mid,y1,y2));if(y2mid)ansmax(ans,query(rs(u),mid1,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(x1lrx2){tag[u].change(1,1,s,y1,y2,h);return ;}if(x1mid)change(ls(u),l,mid,x1,x2,y1,y2,h);if(x2mid)change(rs(u),mid1,r,x1,x2,y1,y2,h);
}
int query(int u,int l,int r,int x1,int x2,int y1,int y2){if(x1lrx2)return mx[u].query(1,1,s,y1,y2);int anstag[u].query(1,1,s,y1,y2);if(x1mid)ansmax(ans,query(ls(u),l,mid,x1,x2,y1,y2));if(x2mid)ansmax(ans,query(rs(u),mid1,r,x1,x2,y1,y2));return ans;
}
int main(){cindsn;for(int i1;in;i){cinabhxy;x;y;hquery(1,1,d,x,xa-1,y,yb-1);change(1,1,d,x,xa-1,y,yb-1,h);}coutmx[1].mx[1]\n;return 0;
}
