【BZOJ 1513】Tet-Tetris 3D【二维线段树】

Description

在新游戏中你将知道落下的立方体信息以及位置,你的任务就是回答所有立方体落下后最高的方块的高度.所有的立方体在下落过程中都是垂直的并且不会旋转.平板左下角坐标为原点,并且平行于坐标轴.

Solution

二维线段树板子题 同时两层树之间的信息不能相互传递。

Code

#include<cstdio> #include<cstring> #include<algorithm> #define N 1010 using namespace std; int n,m; #define lson o << 1 #define rson o << 1 | 1 int LL,RR; struct node{ struct tree{ int maxn[N*3],tag[N*3]; void update(int o,int l,int r,int ll,int rr,int s) { maxn[o] = max(maxn[o],s); if(ll <= l && rr >= r) { tag[o] = max(s,tag[o]); return; } int mid = (l+r)>>1; if(ll <= mid) update(lson,l,mid,ll,rr,s); if(rr > mid) update(rson,mid+1,r,ll,rr,s); } int query(int o,int l,int r,int ll,int rr) { if(ll <= l && rr >= r) return maxn[o]; int mid = (l+r)>>1,ans = tag[o]; if(ll <= mid) ans = max(query(lson,l,mid,ll,rr),ans); if(rr > mid) ans = max(query(rson,mid+1,r,ll,rr),ans); return ans; } }maxn[N*3],tag[N*3]; void update(int o,int l,int r,int ll,int rr,int s) { maxn[o].update(1,1,n,ll,rr,s); if(LL <= l && RR >= r) { tag[o].update(1,1,n,ll,rr,s); return; } int mid = (l+r)>>1; if(LL <= mid) update(lson,l,mid,ll,rr,s); if(RR > mid) update(rson,mid+1,r,ll,rr,s); } int query(int o,int l,int r,int ll,int rr) { if(LL <= l && RR >= r) return maxn[o].query(1,1,n,ll,rr); int mid = (l+r)>>1,ans = tag[o].query(1,1,n,ll,rr); if(LL <= mid) ans = max(query(lson,l,mid,ll,rr),ans); if(RR > mid) ans = max(query(rson,mid+1,r,ll,rr),ans); return ans; } }seg; int main() { int q,d,s,w,x,y; scanf("%d%d%d",&n,&m,&q); while(q--) { scanf("%d%d%d%d%d",&d,&s,&w,&x,&y); LL = x + 1; RR = x + d; int p = seg.query(1,1,n,y+1,y+s); seg.update(1,1,n,y+1,y+s,p+w); } LL = 1,RR = n; printf("%d\n",seg.query(1,1,n,1,n)); return 0; }