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

SuperCowHorse · 2025-08-13 19:57:09 · 题解

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

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

对于区间 [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] 进行第二遍分治就行。由于在第三步时，我们已经按照第二关键字排序，那么在第二次分治中，我们只需要按第三关键字排序，将第四关键字放进树状数组中维护即可。

注意几个坑：

• 排序要排得彻底。例：

  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 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 的顺序。

• 树状数组每一次操作后记得清空。

• 

上面一句话毁了我 2h。

因为多一次分治，复杂度：O(n\log^3 n)。

Code：

#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：德丽莎世界第一可爱！