P3437 [POI 2006] TET-Tetris 3D&&SP1741 TETRIS3D - Tetris 3D题解

· · 题解

安利一下我的博客！

双倍经验！

非常经典的题目。

思路

省流：线段树套线段树、标记永久化。

落下一个方块时，我们需要求出该方块在地面投影的区域中，最高的方块高度 x，然后将该区域的高度统一更改为 x+w。

即：动态维护二维平面赋值、求二维平面的最大值。

这样一来，就不能用树状数组套线段树了，只能用线段树套线段树。

不过，正常的线段树套线段树是无法维护的，这时就有一个神奇的操作——标记永久化。我们先考虑一维的线段树，进行区间操作时，要维护区间最大值 mx 与懒标记 tag，实时 push_down 和 push_up。我们现在要做的就是规避掉 push_down 和 push_up。对于 push_up，由于本题中的高度只增不降，所以修改时，我们直接用 x+w 去尝试更新修改路径上的每一个 mx。对于 push_down，我们直接不干了！这样一来，在求区间 \max 的时候，我们需要对查询路径上的每一个 tag 都取 \max（修改操作只增不降，所以 \max 一定是最新的操作），对于区间完全被覆盖的，我们还需要用答案对 mx 取 \max。

二维线段树也是一样的，对于外层线段树上的每个节点，我们都需要开两棵树，一棵 mx，一棵 tag。

代码

#include<bits/stdc++.h>
using namespace std;
int d,s,n,rt[4005],rtt[4005];
#define mid ((l+r)>>1)
struct js
{
    int tr[2000005],tag[2000005],cnt=0,ls[2000005],rs[2000005];
    void push_down(int p)
    {
        if(!ls[p]) ls[p]=++cnt;
        if(!rs[p]) rs[p]=++cnt;
        tag[ls[p]]=max(tag[ls[p]],tag[p]),tr[ls[p]]=max(tr[ls[p]],tag[p]);
        tag[rs[p]]=max(tag[rs[p]],tag[p]),tr[rs[p]]=max(tr[rs[p]],tag[p]);
        tag[p]=0;
    }
    void push_up(int p)
    {
        tr[p]=max(tr[ls[p]],tr[rs[p]]);
    }
    void update(int &p,int l,int r,int L,int R,int w)
    {
        if(!p) p=++cnt;
        if(L<=l&&R>=r)
        {
            tr[p]=max(tr[p],w),tag[p]=max(tag[p],w);
            return ;
        }
        push_down(p);
        if(L<=mid&&!ls[p]) ls[p]=++cnt;
        if(R>mid&&!rs[p]) rs[p]=++cnt;
        if(L<=mid) update(ls[p],l,mid,L,R,w);
        if(R>mid) update(rs[p],mid+1,r,L,R,w);
        push_up(p); 
    }
    int query(int p,int l,int r,int L,int R)
    {
        if(!p) return 0;
        if(L<=l&&R>=r) return tr[p];
        int res=0;
        push_down(p);
        if(L<=mid) res=max(res,query(ls[p],l,mid,L,R));
        if(R>mid) res=max(res,query(rs[p],mid+1,r,L,R));
        return res;
    }
}tr,trr;
//tr是mx,trr是tag 
void update(int p,int l,int r,int L,int R,int ll,int rr,int w)
{
    tr.update(rt[p],1,s,ll,rr,w);
    if(L<=l&&R>=r)
    {
        trr.update(rtt[p],1,s,ll,rr,w);
        return ;
    }
    if(L<=mid) update(p<<1,l,mid,L,R,ll,rr,w);
    if(R>mid) update((p<<1)|1,mid+1,r,L,R,ll,rr,w);
}
int query(int p,int l,int r,int L,int R,int ll,int rr)
{
    int res=0;
    res=trr.query(rtt[p],1,s,ll,rr);
    if(L<=l&&R>=r)
    {
        res=max(res,tr.query(rt[p],1,s,ll,rr));
        return res;
    }
    if(L<=mid) res=max(res,query(p<<1,l,mid,L,R,ll,rr));
    if(R>mid) res=max(res,query((p<<1)|1,mid+1,r,L,R,ll,rr));
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>d>>s>>n;
    while(n--)
    {
        int dd,ss,w,x,y;
        cin>>dd>>ss>>w>>x>>y;
        x++,y++,update(1,1,d,x,x+dd-1,y,y+ss-1,w+query(1,1,d,x,x+dd-1,y,y+ss-1)); 
    }
    cout<<query(1,1,d,1,d,1,s);
    return 0;
}