P7312 [COCI 2018/2019 #2] Sunčanje题解

· · 题解

安利Blog。

提供一个不用 CDQ 但是非常有意思的做法。

思路

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

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

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

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

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

注意到本题如果一个点被打上标记，那么这个标记就是永久的了，不会被删去，这意味着本题被标记过的点的数量只增不降，这是一个非常好的特殊性质。于是我们将内层线段树改成一个 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;
}