[BZOJ1513/Luogu3437][POI2006]Tet-Tetris 3D(树套树)

发布于 2018-04-17  71 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1513/Luogu3437][POI2006]Tet-Tetris 3D(树套树)

Description

Tetris 3D "Tetris" 游戏的作者决定做一个新的游戏, 一个三维的版本, 在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止. 作者想改变一下游戏的目的使得它更大众化,在新游戏中你将知道落下的立方体信息以及位置,你的任务就是回答所有立方体落下后最高的方块的高度.所有的立方体在下落过程中都是垂直的并且不会旋转.平板左下角坐标为原点,并且平行于坐标轴.

Tag

树套树

解决思路

观察,题目要求的便是取区间最大值和区间覆盖。那么如果是在序列上的操作,直接用线段树来维护就好了,区间最大值可以直接合并得到,而区间覆盖可以用懒标记来实现。
现在转到了二维平面上,那么就用二维线段树来维护,同样维护懒标记,只不过由于不好下放,采用标记永久化的方式。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lson (now<<1)
#define rson (lson|1)

const int maxN=1010;
const int inf=2147483647;

int n,m;

class InSegTree//内层线段树,即普通的线段树,维护y轴信息
{
public:
    int Val[maxN<<2],Lazy[maxN<<2];
    void Modify(int now,int l,int r,int ql,int qr,int key){
        Val[now]=max(Val[now],key);
        if ((l==ql)&&(r==qr))
        {
            Lazy[now]=max(Lazy[now],key);
            return;
        }
        int mid=(l+r)>>1;
        if (qr<=mid) Modify(lson,l,mid,ql,qr,key);
        else if (ql>=mid+1) Modify(rson,mid+1,r,ql,qr,key);
        else
        {
            Modify(lson,l,mid,ql,mid,key);
            Modify(rson,mid+1,r,mid+1,qr,key);
        }
        return;
    }
    int Query(int now,int l,int r,int ql,int qr){
        if ((l==ql)&&(r==qr)) return max(Val[now],Lazy[now]);
        int Ret=Lazy[now];
        int mid=(l+r)>>1;
        if (qr<=mid) return max(Ret,Query(lson,l,mid,ql,qr));
        else if (ql>=mid+1) return max(Ret,Query(rson,mid+1,r,ql,qr));
        else return max(Ret,max(Query(lson,l,mid,ql,mid),Query(rson,mid+1,r,mid+1,qr)));
    }
};

class OutSegTree//外层线段树,维护x轴信息
{
public:
    InSegTree Val[maxN<<2],Lazy[maxN<<2];//外层线段树的每一个节点都是一棵内层线段树,注意懒标记也要用线段树来维护
    void Modify(int now,int l,int r,int ql,int qr,int p,int q,int key){
        Val[now].Modify(1,1,m,p,q,key);
        if ((l==ql)&&(r==qr))
        {
            Lazy[now].Modify(1,1,m,p,q,key);
            return;
        }
        int mid=(l+r)>>1;
        if (qr<=mid) Modify(lson,l,mid,ql,qr,p,q,key);
        else if (ql>=mid+1) Modify(rson,mid+1,r,ql,qr,p,q,key);
        else
        {
            Modify(lson,l,mid,ql,mid,p,q,key);
            Modify(rson,mid+1,r,mid+1,qr,p,q,key);
        }
        return;
    }
    int Query(int now,int l,int r,int ql,int qr,int p,int q){
        if ((l==ql)&&(r==qr)) return Val[now].Query(1,1,m,p,q);
        int mid=(l+r)>>1;
        int Ret=Lazy[now].Query(1,1,m,p,q);
        if (qr<=mid) return max(Ret,Query(lson,l,mid,ql,qr,p,q));
        else if (ql>=mid+1) return max(Ret,Query(rson,mid+1,r,ql,qr,p,q));
        else return max(Ret,max(Query(lson,l,mid,ql,mid,p,q),Query(rson,mid+1,r,mid+1,qr,p,q)));
    }
};

OutSegTree S;

int main()
{
    ios::sync_with_stdio(false);
    int Q;
    cin>>n>>m>>Q;n++;m++;
    while (Q--)
    {
        int d,s,w,x,y;cin>>d>>s>>w>>x>>y;x++;y++;
        w=w+S.Query(1,1,n,x,x+d-1,y,y+s-1);
        S.Modify(1,1,n,x,x+d-1,y,y+s-1,w);
    }
    cout<<S.Query(1,1,n,1,n,1,m)<<endl;
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1513/Luogu3437][POI2006]Tet-Tetris 3D(树套树)


HNCJ OIer