关于树套树的两个小trick

zpy12345 · 2026-04-26 10:47:58 · 算法·理论

众所周知，写线段树套线段树时有一些非常神奇的小技巧。

标记永久化

Link。

非常经典的题目。

思路

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

落下一个方块时，我们需要求出该方块在地面投影的区域中，最高的方块高度 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;
}

线段树的内层不一定要是线段树

Link。

思路

我们可以倒着枚举矩形，这样一来，我们只需要维护一个数据结构使其能够完成以下操作：

将一个矩形内的点都打上标记。
判断一个矩形内有没有点被打过标记。

这不就是线段树套线段树的板子吗？但是本题非常之阴，用线段树套线段树会被卡空间！（提交记录）于是我们不得不考虑另辟蹊径~~我也真是服了~~。

考虑线段树套线段树的外层线段树不变，内层线段树我们换成其它的某个数据结构/算法，要求其支持以下操作；

将一个区间（一维）内的点都打上标记。
判断一个区间（一维）内有没有点被打过标记。

注意到本题如果一个点被打上标记，那么这个标记就是永久的了，不会被删去，这意味着本题被标记过的点的数量只增不降，这是一个非常好的特殊性质。于是我们将内层线段树改成一个 set 维护二元组 \left ( l,r \right ) ，表示 \left ( l,r \right ) 区间都有标记。这里我们要求 set 中维护的区间两两不交。

对于打标记操作，我们只需要将所有与新加入区间有交集的区间都删去，然后将一个大区间（这些区间的并集）加入 set。由于每个区间只会被加入一次删除一次，故时间复杂度与线段树复杂度相同（找区间需要二分！）。

对于查询操作则更简单了，只需要看看 set 里的区间与询问区间有没有交即可，依旧二分。

时间复杂度 O(n\log^2_{}{n} )，空间复杂度 O(n\log_{}{n} )。

代码

理解了代码就很煎蛋了，不理解可以看看代码加深理解。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;//离散化后有二倍的点
int n,nx,ny;
struct js
{
    int x,y,a,b;
}a[N];
map<int,bool> mpx,mpy;
map<int,int> mppx,mppy;
bool ans[N];
struct jss
{
    set<pair<int,int> > tr[N<<2];
    //因为pair是按first为第一关键字排序的,所以我把(l,r)颠倒过来存的
    void update(int p,int l,int r)
    {
        auto x=tr[p].lower_bound({l,0});
        while(x!=tr[p].end())
        {
            if((*x).second<=l) l=(*x).second,r=max(r,(*x).first),tr[p].erase(x);
            else 
            {
                if((*x).second>r) break;
                r=max(r,(*x).first),tr[p].erase(x);
            }
            x=tr[p].lower_bound({l,0});
        }
        tr[p].insert({r,l});
    }
    bool query(int p,int l,int r)
    {
        auto x=tr[p].lower_bound({l,0});
        bool res=0;
        if(x!=tr[p].end()&&(*x).second<=r) res=1;
        return res;
    }
}tr,mx;
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((l+r)>>1)
void update(int p,int l,int r,int L,int R,int ll,int rr)
{
    if(L<=l&&R>=r)
    {
        mx.update(p,ll,rr);
        return ;
    }
    tr.update(p,ll,rr);
    if(L<=mid) update(ls,l,mid,L,R,ll,rr);
    if(R>mid) update(rs,mid+1,r,L,R,ll,rr);
}
bool query(int p,int l,int r,int L,int R,int ll,int rr)
{
    if(L<=l&&R>=r) return tr.query(p,ll,rr)|mx.query(p,ll,rr);
    bool res=mx.query(p,ll,rr);
    if(L<=mid&&(!res)) res=query(ls,l,mid,L,R,ll,rr);
    if(R>mid&&(!res)) res=query(rs,mid+1,r,L,R,ll,rr);
    return res;
}
int main()
{   
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].a>>a[i].b;
        mpx[a[i].x+1]=mpx[a[i].x+a[i].a]=1,mpy[a[i].y+1]=mpy[a[i].y+a[i].b]=1;
        //离散化方式过于猎奇,请不要在意.
    }
    //其实不离散化应该也行
    for(auto it:mpx) mppx[it.first]=++nx;
    for(auto it:mpy) mppy[it.first]=++ny;
    mpx.clear(),mpy.clear();
    for(int i=n;i>=1;i--)
        a[i].a=mppx[a[i].x+a[i].a],a[i].b=mppy[a[i].y+a[i].b],a[i].x=mppx[a[i].x+1],a[i].y=mppy[a[i].y+1];
    mppx.clear(),mppy.clear();
    for(int i=n;i>=1;i--) 
        ans[i]=query(1,1,nx,a[i].x,a[i].a,a[i].y,a[i].b),update(1,1,nx,a[i].x,a[i].a,a[i].y,a[i].b);
    for(int i=1;i<=n;i++)
        if(ans[i]) cout<<"NE\n";
        else cout<<"DA\n";
    return 0;
}

完结撒花！求管理员过审！