首页 > 代码库 > BZOJ 1513 [POI2006]Tet-Tetris 3D（二维线段树）
BZOJ 1513 [POI2006]Tet-Tetris 3D（二维线段树）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1513
【题目大意】
一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.
你将知道落下的立方体信息以及位置,
你的任务就是回答所有立方体落下后最高的方块的高度.
所有的立方体在下落过程中都是垂直的并且不会旋转.平板左下角坐标为原点,
并且平行于坐标轴.
【题解】
二维线段树维护区间最大值，最大值标记永久化即可。
【代码】
#include <cstdio>#include <algorithm>using namespace std;int D,S,N,ql,qr,qd,qu;struct segx{ int v[3010],tag[3010]; void change(int k,int l,int r,int x,int y,int val){ v[k]=max(v[k],val); if(l==x&&y==r){tag[k]=max(tag[k],val);return;} int mid=(l+r)>>1; if(x<=mid)change(k<<1,l,mid,x,min(mid,y),val); if(y>mid)change(k<<1|1,mid+1,r,max(x,mid+1),y,val); } int query(int k,int l,int r,int x,int y){ if(l==x&&y==r)return v[k]; int mid=(l+r)>>1,ans=tag[k]; if(x<=mid)ans=max(ans,query(k<<1,l,mid,x,min(mid,y))); if(y>mid)ans=max(ans,query(k<<1|1,mid+1,r,max(x,mid+1),y)); return ans; }};struct segy{ segx v[3010],tag[3010]; void change(int k,int l,int r,int x,int y,int val){ v[k].change(1,1,S,qd,qu,val); if(l==x&&y==r){tag[k].change(1,1,S,qd,qu,val);return;} int mid=(l+r)>>1; if(x<=mid)change(k<<1,l,mid,x,min(mid,y),val); if(y>mid)change(k<<1|1,mid+1,r,max(x,mid+1),y,val); } int query(int k,int l,int r,int x,int y){ if(l==x&&y==r)return v[k].query(1,1,S,qd,qu); int mid=(l+r)>>1,ans=tag[k].query(1,1,S,qd,qu); if(x<=mid)ans=max(ans,query(k<<1,l,mid,x,min(mid,y))); if(y>mid)ans=max(ans,query(k<<1|1,mid+1,r,max(x,mid+1),y)); return ans; }}T;int main(){ scanf("%d%d%d",&D,&S,&N); for(int i=1;i<=N;i++){ int d,s,w,x,y; scanf("%d%d%d%d%d",&d,&s,&w,&x,&y); ql=x+1;qr=x+d;qd=y+1;qu=y+s; int ans=T.query(1,1,D,ql,qr); T.change(1,1,D,ql,qr,ans+w); }qd=1,qu=S; printf("%d\n",T.query(1,1,D,1,D)); return 0;}BZOJ 1513 [POI2006]Tet-Tetris 3D（二维线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。