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 Sample Output 6
將x與y看作一個二維平面
每個立方體的下落可以看作查詢矩陣 (x+1,y+1) (x+d,y+s) 內的最大值并將矩陣內所有值變為maxh+w
考慮樹套樹(二維線段樹)的做法 我們發現標記下傳(pushdown)與信息上傳(pushup)很難辦到
這時標記永久化派上用場了
那標記永久化是個啥呢？
在寫普通線段樹時 我們對修改的區間打上標記 并在查詢的時候下放標記并更新答案
那么我們是否可以不對標記進行下放 在路過該節點(需要用到它或它兒子的信息)的時候把修改對答案的影響加上 來省去標記下放的過程呢？
吼哇！
于是我們yy了一個新的不用pushdown的線段樹
新線段樹的每個節點維護 sum 與 all 兩個標記
分別代表 區間和 與 節點所表示的區間都被加了多少
sum也可以看作該節點所表示的區間內有一些地方被加上了一些值 它們的和為sum(具體位置我們不關心)
修改操作就相當于一路更新所經過節點的sum值 直到目標區間與當前結點區間完全覆蓋 更新該點的all值
查詢操作與修改操作正好相反 計算所經過節點的all值對答案的貢獻 直到目標區間與當前結點區間完全覆蓋 并用該節點的sum值更新答案
上幾個圖理解一下吧：
sum則代替了信息上傳的過程 維護該節點所表示區間的信息 而信息上傳已經在我們進行修改操作的時候順便做了
因此不再需要信息上傳(pushup)與標記下傳(pushdown)兩個操作
回到本題 對于第一維 我們也可以維護這樣的兩個值 all 與 have
分別代表 該區間全變成了all
與該區間內有一些點變為了have
然后第二維用 普通 or 標記永久化 線段樹來維護這兩個值即可。
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define MAXN 2505#define LL long longusing namespace std;int read(){ int f=1,t=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();} return t*f;}/*----- head -----*/#define ls (cnt<<1)#define rs ((cnt<<1)+1)#define mid ((l+r)>>1)int n,m,p;struct trey{ int all[MAXN],have[MAXN]; void update(int l,int r,int y1,int y2,int v,int cnt) { if(l==y1&&r==y2){all[cnt]=max(all[cnt],v);return;} have[cnt]=max(have[cnt],v); if(y2<=mid) update(l,mid,y1,y2,v,ls); else if(y1>mid) update(mid+1,r,y1,y2,v,rs); else update(l,mid,y1,mid,v,ls),update(mid+1,r,mid+1,y2,v,rs); } int query(int l,int r,int y1,int y2,int cnt) { int ans=all[cnt]; if(l==y1&&r==y2) return max(ans,have[cnt]); if(y2<=mid) return max(ans,query(l,mid,y1,y2,ls)); if(y1>mid) return max(ans,query(mid+1,r,y1,y2,rs)); ans=max(ans,query(l,mid,y1,mid,ls)); ans=max(ans,query(mid+1,r,mid+1,y2,rs)); return ans; }};struct trex{ trey have[MAXN],all[MAXN]; void update(int l,int r,int x1,int x2,int y1,int y2,int v,int cnt) { if(l==x1&&r==x2){all[cnt].update(1,m,y1,y2,v,1);return;} have[cnt].update(1,m,y1,y2,v,1); if(x2<=mid) update(l,mid,x1,x2,y1,y2,v,ls); else if(x1>mid) update(mid+1,r,x1,x2,y1,y2,v,rs); else update(l,mid,x1,mid,y1,y2,v,ls),update(mid+1,r,mid+1,x2,y1,y2,v,rs); } int query(int l,int r,int x1,int x2,int y1,int y2,int cnt) { int ans=all[cnt].query(1,m,y1,y2,1); if(l==x1&&r==x2) return max(ans,have[cnt].query(1,m,y1,y2,1)); if(x2<=mid) return max(ans,query(l,mid,x1,x2,y1,y2,ls)); if(x1>mid) return max(ans,query(mid+1,r,x1,x2,y1,y2,rs)); ans=max(ans,query(l,mid,x1,mid,y1,y2,ls)); ans=max(ans,query(mid+1,r,mid+1,x2,y1,y2,rs)); return ans; }}T;int main(){ n=read(),m=read(),p=read(); while(p--) { int d=read(),s=read(),w=read(),x=read(),y=read(),maxh; maxh=T.query(1,n,x+1,x+d,y+1,y+s,1); T.update(1,n,x+1,x+d,y+1,y+s,maxh+w,1); } printf("%d/n",T.query(1,n,1,n,1,m,1)); return 0;}注意本題矩形內的最大值只會變的越來越大 所以信息上傳時不會用到左右兒子的信息 使用標記永久化就不會出現問題
若答案并不是單調遞增的
那么我們在更新答案的時候就會出現問題 因為我們并不知道標記打上的順序是誰在前誰在后
新聞熱點
疑難解答
