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

· · 题解

Preface

这题俩 cdq 分治题解都被 hack 了。。

于是乎写一篇能过 hack 数据的使用 cdq 分治的题解。

这里与之前两篇题解程序的唯一区别就是：

这道题讨论里说到的，对于 cdq 分治使用 sort 排序时，每一次的比较都必须要彻底才行，体现到代码就是：

（比如这是第一维的排序）

inline bool CmpD1(Query a,Query b){
    if(a.d1!=b.d1) return a.d1<b.d1;
    if(a.d2!=b.d2) return a.d2<b.d2;
    if(a.d3!=b.d3) return a.d3<b.d3;
    return a.d4<b.d4;
}

Problem

四维上升子序列，每个点有权值，问权值之和的最大值是多少。

Solution

首先，这道题很明显就是可以 dp 来做，我们设 dp_j 表示我们最后干掉的崩坏兽是 j 的最大收益。

那么很明显转移就是

{\underset {health[j]\geq health[i] , energy[j]\geq energy[i] , attack[j]\geq attack[i] , defense[j]\geq defense[i]health[j]≥health[i],energy[j]≥energy[i],attack[j]≥attack[i],defense[j]≥defense[i]}{\operatorname {max} }} \quad dp_i+collapse[j]

后面的式子很简单，重要的那么就是前面的偏序的判定条件。

四个不等关系，很明显是四维偏序，所以我们可以使用 cdq 分治解决四维偏序来优化这个 dp 。

那么四维偏序其实就是 排序+cdq+cdq+树状数组 分别解决四维问题，而最后一维的树状数组同时也用于维护最大值。

具体就是，首先我们在最外层对第一维排序，那么此时我们进入第一层 cdq 的时候，第一维是有序的。

那么此时我们在第一层 cdq 中再对第二维排序，具体来说就是把每个元素根据第一维分成 L/R ，也就是说，对于一个点我们在更里层算贡献的时候，只有可能是 L 对 R 方产生贡献。

于是我们带着这一个标记进入下一层并在统计贡献和修改贡献的时候判断一下即可。

也就是说，现在我们的问题变成了一个三维偏序问题，只是带了一个 L/R 的特判，我们现在也保证了第一维的有序，所以已经不用管了，剩下的三维就是一个标准的三位偏序。

我们可以在第一层 cdq 分治分类过后，就进入三维偏序的解决，即 cdq+树状数组。

至此问题得到解决。

还有要注意的就是由于我们这里是 dp ，所以我们不能用后序遍历来做，而是必须使用中序遍历的 cdq 分治的形式来做，因为在处理每一个点的时候，我们需要保证在这个点之前的所有点都已经被更新完毕了。

Code

代码写的太丑了，常数巨大多。

#include<bits/stdc++.h>
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T>
inline void read(T &x){
    x=0;char ch=getchar();bool f=false;
    while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
}
template <typename T>
inline void write(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
    return ;
}
#define ll long long
const int N=2e5+5,LEFT=-1,RIGHT=1;
const ll INF=1e15+7;
int n,m,k,Cnt,Acnt,idx,top;
ll Ans,dp[N],a[N],b[N],c[N];
struct Query{ll d1,d2,d3,d4,part,id,val;}Q[N],Q1[N],Q2[N];
void Add(int x,ll v){for(;x<=idx;x+=(x&(-x))) c[x]=max(c[x],v);}
ll Ask(int x){ll res=-INF;for(;x;x-=(x&(-x))) res=max(res,c[x]);return res;}
void Clear(int x){for(;x<=idx;x+=(x&(-x))) c[x]=-INF;return ;}
inline bool CmpD1(Query a,Query b){
    if(a.d1!=b.d1) return a.d1<b.d1;
    if(a.d2!=b.d2) return a.d2<b.d2;
    if(a.d3!=b.d3) return a.d3<b.d3;
    return a.d4<b.d4;
}
inline bool CmpD2(Query a,Query b){
    if(a.d2!=b.d2) return a.d2<b.d2;
    if(a.d3!=b.d3) return a.d3<b.d3;
    if(a.d4!=b.d4) return a.d4<b.d4;
    return a.d1<b.d1;
}
inline bool CmpD3(Query a,Query b){
    if(a.d3!=b.d3) return a.d3<b.d3;
    if(a.d4!=b.d4) return a.d4<b.d4;
    if(a.d1!=b.d1) return a.d1<b.d1;
    return a.d2<b.d2;
}
inline bool CmpD4(Query a,Query b){
    if(a.d4!=b.d4) return a.d4<b.d4;
    if(a.d1!=b.d1) return a.d1<b.d1;
    if(a.d2!=b.d2) return a.d2<b.d2;
    return a.d3<b.d3;
}
void CDQ_Divide_3D(int l,int r){
    if(l==r) return ;
    int mid=l+r>>1;
    CDQ_Divide_3D(l,mid);
    for (int i=l;i<=r;i++) Q2[i]=Q1[i];
    sort(Q2+l,Q2+mid+1,CmpD3),sort(Q2+mid+1,Q2+r+1,CmpD3);
    for(int i=mid+1,j=l;i<=r;i++){
        while(Q2[i].d3>=Q2[j].d3&&j<=mid){
            if(Q2[j].part==LEFT) Add(Q2[j].d4,dp[Q2[j].id]);
            j++;
        }
        if(Q2[i].part==RIGHT) dp[Q2[i].id]=max(dp[Q2[i].id],Ask(Q2[i].d4)+Q2[i].val); 
    }
    for(int i=l;i<=mid;i++) if(Q2[i].part==LEFT) Clear(Q2[i].d4);
    CDQ_Divide_3D(mid+1,r);
    return ;
}
void CDQ_Divide_2D(int l,int r){
    if(l==r) return ;
    int mid=l+r>>1;
    CDQ_Divide_2D(l,mid);
    for(int i=l;i<=r;i++) Q1[i]=Q[i],Q1[i].part=(i<=mid?-1:1);
    sort(Q1+l,Q1+r+1,CmpD2);
    CDQ_Divide_3D(l,r);
    CDQ_Divide_2D(mid+1,r);
    return ;
}
signed main(){
    read(n);
    for(int i=1;i<=n;i++) read(Q[i].d1),read(Q[i].d2),read(Q[i].d3),read(Q[i].d4),read(a[i]),Q[i].id=i,b[++top]=Q[i].d4,Q[i].val=a[i];
    sort(b+1,b+top+1);idx=unique(b+1,b+top+1)-b-1;
    for(int i=1;i<=n;i++) Q[i].d4=lower_bound(b+1,b+idx+1,Q[i].d4)-b,c[i]=-INF;
    sort(Q+1,Q+n+1,CmpD1);top=0;
    for(int i=1;i<=n;i++){
        if(Q[i].d1==Q[i-1].d1&&Q[i].d2==Q[i-1].d2&&Q[i].d3==Q[i-1].d3&&Q[i].d4==Q[i-1].d4) Q[top].val+=max(1ll*0,Q[i].val);
        else Q[++top]=Q[i],Q[top].id=top;
    }
    n=top;for(int i=1;i<=n;i++) dp[i]=Q[i].val;
    CDQ_Divide_2D(1,n);
    for(int i=1;i<=n;i++) Ans=max(Ans,dp[i]);
    write(Ans);
    return 0;
}