题解：P5621 [DBOI2019] 德丽莎世界第一可爱

首先，拿到题目，容易知道这是一道四维偏序题。

回想一下我们三维偏序是怎么做的？

对于区间

[l,r]

（假设已按第一关键字排序）：

求出 $mid=\lfloor\frac{l+r}2\rfloor$ 。
遍历 $[l,mid]$ 。
对区间 $[l,r]$ 按第二关键字排序。对于每一个 $lx\in [l,mid]$ 且 $rx\in [mid+1,r]$ 的区间 $[lx,rx]$ ，统计答案。此处可以用权值树状数组维护区间 $[1,x]$ 的最大值。
遍历 $[mid+1,r]$ 。

容易发现，三维偏序的复杂度是

O(n\log^2 n)

的。

那如何解决四维偏序的问题呢？

只需要在第三步更新答案时，再对于

[l,r]

进行第二遍分治就行。由于在第三步时，我们已经按照第二关键字排序，那么在第二次分治中，我们只需要按第三关键字排序，将第四关键字放进树状数组中维护即可。

注意几个坑：

排序要排得彻底。例：

CPP

inline bool cmp3(Honkai u,Honkai v){
    if(u.c!=v.c) return u.c<v.c;
    if(u.d!=v.d) return u.d<v.d;
    if(u.a!=v.a) return u.a<v.a;
    return u.b<v.b;
}

以上代码是正确的。

CPP

inline bool cmp3(Honkai u,Honkai v){
    if(u.c!=v.c) return u.c<v.c;
    return u.d<v.d;
}

以上代码是错误的，因为 sort 不是稳定排序，可能会破坏已有的偏序关系。当然你也可以写 stable_sort。不过会多

\log n

的复杂度。

使用临时数组存储 $a$ ，不能破坏原有 $a$ 的顺序。
树状数组每一次操作后记得清空。
$i$ 和 $j$ 别写反了。

~~上面一句话毁了我 2h。~~

因为多一次分治，复杂度：

O(n\log^3 n)

。

Code：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e4+5;
int N=2e5;
int n,m,p[maxn<<2];struct Honkai{int a,b,c,d,id;ll Theresa;bool g;}b[maxn],a[maxn],o[maxn],oo[maxn];//o 和 oo 是临时数组
map<int,int>mp;ll ans,f[maxn];
struct BITS{
    ll c[maxn<<2];
    inline int lowbit(int x){return x&(-x);}
    inline void add(int p,ll v){
        for(;p<=N;p+=lowbit(p)){
            c[p]=max(c[p],v);
        }
    }
    inline ll query(int p){
        ll res=-1e18;
        for(;p;p-=lowbit(p)){
            res=max(res,c[p]);
        }
        return res;
    }
    inline void init(int p){
        for(;p<=N;p+=lowbit(p)){
            c[p]=-1e18;
        }
    }
}t;//树状数组
inline bool cmp1(Honkai u,Honkai v){
    if(u.a!=v.a) return u.a<v.a;
    if(u.b!=v.b) return u.b<v.b;
    if(u.c!=v.c) return u.c<v.c;
    if(u.d!=v.d) return u.d<v.d;
    return u.Theresa>v.Theresa;
}
inline bool cmp2(Honkai u,Honkai v){
    if(u.b!=v.b) return u.b<v.b;
    if(u.c!=v.c) return u.c<v.c;
    if(u.d!=v.d) return u.d<v.d;
    return u.a<v.a;
}
inline bool cmp3(Honkai u,Honkai v){
    if(u.c!=v.c) return u.c<v.c;
    if(u.d!=v.d) return u.d<v.d;
    if(u.a!=v.a) return u.a<v.a;
    return u.b<v.b;
}
inline void cdq2(int l,int r){//第二次分治
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq2(l,mid);
    for(int i=l;i<=r;++i){
        o[i]=oo[i];
    }
    sort(o+l,o+mid+1,cmp3);//按第三关键字排序
    sort(o+mid+1,o+r+1,cmp3);
    int i=l,j=mid+1;
    for(;i<=mid&&j<=r;){
        if(o[j].c<o[i].c){
            if(!o[j].g) f[o[j].id]=max(f[o[j].id],t.query(o[j].d)+o[j].Theresa);
            ++j;
        }
        else{
            if(o[i].g) t.add(o[i].d,f[o[i].id]);
            ++i;
        }
    }
    for(;j<=r;){
        if(!o[j].g) f[o[j].id]=max(f[o[j].id],t.query(o[j].d)+o[j].Theresa);
        ++j;
    }
    for(int k=l;k<i;++k){
        if(o[k].g) t.init(o[k].d);
    }
    cdq2(mid+1,r);
}
inline void cdq1(int l,int r){//第一次分治
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq1(l,mid);
    for(int i=l;i<=r;++i){
        oo[i]=a[i];
    }
    for(int i=l;i<=mid;++i){
        oo[i].g=1;
    }
    for(int i=mid+1;i<=r;++i){
        oo[i].g=0;
    }
    sort(oo+l,oo+r+1,cmp2);//按第二关键字排序
    cdq2(l,r);
    cdq1(mid+1,r);
}
inline void solve(){
    scanf("%d",&n);ans=-1e18;
    for(int i=1;i<=n;++i){
        scanf("%d%d%d%d%lld",&b[i].a,&b[i].b,&b[i].c,&b[i].d,&b[i].Theresa);
        p[++m]=b[i].a;
        p[++m]=b[i].b;
        p[++m]=b[i].c;
        p[++m]=b[i].d;
        ans=max(ans,b[i].Theresa);
        b[i].id=i;
    }
    sort(p+1,p+m+1);//离散化
    m=unique(p+1,p+m+1)-p-1;
    for(int i=1;i<=m;++i){
        mp[p[i]]=i;
    }
    for(int i=1;i<=n;++i){
        b[i].a=mp[b[i].a];
        b[i].b=mp[b[i].b];
        b[i].c=mp[b[i].c];
        b[i].d=mp[b[i].d];
    }
    N=m;m=0;sort(b+1,b+1+n,cmp1);//先按第一关键字排序
    for(int i=1;i<=n;++i){
        if(b[i].a==b[i-1].a&&b[i].b==b[i-1].b&&b[i].c==b[i-1].c&&b[i].d==b[i-1].d){
            a[m].Theresa+=max(0ll,b[i].Theresa);
        }
        else a[++m]=b[i],a[m].id=m;
    }
    n=m;for(int i=1;i<=n;++i) f[i]=a[i].Theresa;
    for(int i=1;i<=N;++i) t.init(i);
    sort(a+1,a+n+1,cmp1);
    cdq1(1,n);
    for(int i=1;i<=n;++i){
        ans=max(ans,f[i]);
    }
    printf("%lld\n",ans);
}
signed main(){
    // freopen("a.txt","r",stdin);
    int T=1;for(;T;--T) solve();
    return 0;
}

PS：德丽莎世界第一可爱！

题解：P5621 [DBOI2019] 德丽莎世界第一可爱

文章操作

相关推荐

评论

题解：P5621 [DBOI2019] 德丽莎世界第一可爱