首页 > 代码库 > BZOJ1513: [POI2006]Tet-Tetris 3D
BZOJ1513: [POI2006]Tet-Tetris 3D
1513: [POI2006]Tet-Tetris 3D
Time Limit: 30 Sec Memory Limit: 162 MBSubmit: 544 Solved: 176
[Submit][Status]
Description
Task: Tetris 3D"Tetris" 游戏的作者决定做一个新的游戏, 一个三维的版本, 在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止. 作者想改变一下游戏的目的使得它更大众化,在新游戏中你将知道落下的立方体信息以及位置,你的任务就是回答所有立方体落下后最高的方块的高度.所有的立方体在下落过程中都是垂直的并且不会旋转.平板左下角坐标为原点,并且平行于坐标轴.
Input
第一行给出三个整数 D, S and N ( 1<= N<= 20 000, 1<= D, S <=1 000), 分别表示平板的长和宽以及下落立方体的数目. 接下来N 行每行描述一个立方体. 每行包含5个整数: d, s, w, x and y (1<= d, 0 <=x, d + x<= D, 1 <=s, 0<= y, s + y<= S, 1<= w <=100 000), 分别表示立方体的长\宽\高以及落下的左下角坐标, 长和宽都是平行于平板坐标轴的,落下后立方体着地的四个角坐标分别为: (x, y), (x + d, y), (x, y + s) and (x + d, y + s).
Output
一个整数表示所有立方体落下后最高的方块的高度.
Sample Input
7 5 4
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2
Sample Output
6
HINT
Source
题解：
乍一看，这不是线段树裸题吗，我擦，居然是二维的。。。
我好像还没有写过二维线段树。。。
然后发现了这样一份诡异的二维线段树。。。比较diao的就是它维护了两棵线段树！
内线段树和普通的一样，不过它是这样更新和查询的：
int query(int k,int l,int r,int x,int y) { if(l==x&&r==y)return mx[k]; int mid=(l+r)>>1,ans=tag[k]; if(y<=mid)return max(ans,query(k<<1,l,mid,x,y)); else if(x>mid)return max(ans,query(k<<1|1,mid+1,r,x,y)); else return max(ans,max(query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y))); } void change(int k,int l,int r,int x,int y,int z) { mx[k]=max(mx[k],z); if(l==x&&r==y){tag[k]=max(tag[k],z);return;} int mid=(l+r)>>1; if(y<=mid)change(k<<1,l,mid,x,y,z); else if(x>mid)change(k<<1|1,mid+1,r,x,y,z); else change(k<<1,l,mid,x,mid,z),change(k<<1|1,mid+1,r,mid+1,y,z); }
也就是说，它没有标记下传！查询的时候直接用当前节点的tag（一定是全部覆盖的，所以是有效的）和各子树的最优值比较，就可以得出ans，orz！
然后外层线段树和里层的基本就一样了。
seg mx[4*maxn],tag[4*maxn]; int query(int k,int l,int r,int x,int y) { if(l==x&&r==y)return mx[k].query(1,1,m,yl,yr); int mid=(l+r)>>1,ans=tag[k].query(1,1,m,yl,yr); if(y<=mid)return max(ans,query(k<<1,l,mid,x,y)); else if(x>mid)return max(ans,query(k<<1|1,mid+1,r,x,y)); else return max(ans,max(query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y))); } void change(int k,int l,int r,int x,int y,int z) { mx[k].change(1,1,m,yl,yr,z); if(l==x&&r==y){tag[k].change(1,1,m,yl,yr,z);return;} int mid=(l+r)>>1; if(y<=mid)change(k<<1,l,mid,x,y,z); else if(x>mid)change(k<<1|1,mid+1,r,x,y,z); else change(k<<1,l,mid,x,mid,z),change(k<<1|1,mid+1,r,mid+1,y,z); }
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 705 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,q,xl,xr,yl,yr; 61 struct seg 62 { 63 int mx[4*maxn],tag[4*maxn]; 64 int query(int k,int l,int r,int x,int y) 65 { 66 if(l==x&&r==y)return mx[k]; 67 int mid=(l+r)>>1,ans=tag[k]; 68 if(y<=mid)return max(ans,query(k<<1,l,mid,x,y)); 69 else if(x>mid)return max(ans,query(k<<1|1,mid+1,r,x,y)); 70 else return max(ans,max(query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y))); 71 } 72 void change(int k,int l,int r,int x,int y,int z) 73 { 74 mx[k]=max(mx[k],z); 75 if(l==x&&r==y){tag[k]=max(tag[k],z);return;} 76 int mid=(l+r)>>1; 77 if(y<=mid)change(k<<1,l,mid,x,y,z); 78 else if(x>mid)change(k<<1|1,mid+1,r,x,y,z); 79 else change(k<<1,l,mid,x,mid,z),change(k<<1|1,mid+1,r,mid+1,y,z); 80 } 81 }; 82 struct segg 83 { 84 seg mx[4*maxn],tag[4*maxn]; 85 int query(int k,int l,int r,int x,int y) 86 { 87 if(l==x&&r==y)return mx[k].query(1,1,m,yl,yr); 88 int mid=(l+r)>>1,ans=tag[k].query(1,1,m,yl,yr); 89 if(y<=mid)return max(ans,query(k<<1,l,mid,x,y)); 90 else if(x>mid)return max(ans,query(k<<1|1,mid+1,r,x,y)); 91 else return max(ans,max(query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y))); 92 } 93 void change(int k,int l,int r,int x,int y,int z) 94 { 95 mx[k].change(1,1,m,yl,yr,z); 96 if(l==x&&r==y){tag[k].change(1,1,m,yl,yr,z);return;} 97 int mid=(l+r)>>1; 98 if(y<=mid)change(k<<1,l,mid,x,y,z); 99 else if(x>mid)change(k<<1|1,mid+1,r,x,y,z);100 else change(k<<1,l,mid,x,mid,z),change(k<<1|1,mid+1,r,mid+1,y,z);101 }102 }; 103 segg a;104 105 int main()106 107 {108 109 freopen("input.txt","r",stdin);110 111 freopen("output.txt","w",stdout);112 113 n=read();m=read();q=read();114 while(q--)115 {116 int d=read(),s=read(),w=read(),x=read(),y=read();117 xl=x+1;xr=x+d;yl=y+1;yr=y+s;118 int h=a.query(1,1,n,xl,xr)+w;119 a.change(1,1,n,xl,xr,h);120 }121 xl=yl=1;xr=n;yr=m;122 printf("%d\n",a.query(1,1,n,1,n));123 124 return 0;125 126 }
BZOJ1513: [POI2006]Tet-Tetris 3D
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。