BZOJ1513: [POI2006]Tet-Tetris 3D

1513: [POI2006]Tet-Tetris 3D

Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 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

Sample Output

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
",a.query(1,1,n,1,n));
123 
124     return 0;
125 
126 }

View Code