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

· · 题解

CDQ套CDQ 解法

这算是四维偏序的模板题了，做完这道题目珂以尝试做更难一点的模板：P4849 寻找宝藏

常用解决偏序问题的方法有三种：（假设是 k 维偏序）

这道题目适合用前两种方法，这里介绍 CDQ 套 CDQ 做法。

思考一下三维偏序中的 CDQ 分治做法：

本质就是把每个 (x,y,z) 转化若干为 (0,y,z) 对 (1,y,z) 的贡献。剩下的就是个经典二维偏序问题。

四维偏序中珂以沿用三维偏序中的思路。

把若干 (x,y,z,w) 分成 (0/1,0/1,z,w)，然后计算 (0,0,z,w) 对 (1,1,z,w) 的贡献。

第二层 CDQ 和三维偏序中的 CDQ 差不多。

每个元素需要再加个变量 ok 。名字随便取，表示的意思就是第一维的 0/1 情况。（我代码里使用的时候当 ok 为 true 的时候表示的第一维的情况是 0 )

第一层C DQ 的时候把 l\sim mid 这一段的 ok 设成 true （即第一维为 0 ），mid+1\sim r 这一段的 ok 设成 false。

第二层的改变是：插入的时候只用当 ok=true 的时候才能插入，询问的时候只有当 ok=false 的时候才能询问。

同样这个做法可以扩展到 k 维：用若干个变量记录前面几维的 0/1 状态。（然鹅这时候谁还会用 CDQ 呢¿）

有个小细节：《陌上花开》 那道题可以先递归求 l\sim mid 和 mid+1\sim r 然后再合并两边求贡献。但是这道题目是求最长上升序列所以递归求完 l\sim mid 就要计算左边对右边的贡献了，最后才能递归计算 mid+1\sim r。

时间：\mathcal{O}(n\log^3 n)

空间：\mathcal{O}(n)

如果你写的优秀一点应该能跑过 KD-tree。

我写的代码没有复制序列，只是用了个 _pos_1d 和 _pos_2d 辅助还原序列。（如果都不做的话就只能重新 sort 一遍然后常数就翻倍了）

code：

相比KD-tree，代码还是炒鸡短的，连2.5k都不到。

下边这个代码的 CDQ 部分有点压行，不压行且带详细注释的代码去这里看-> here

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 500050
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3fll;
int n,b[N],bn,_pos_2d[N],_pos_1d[N];
ll ans;
struct QAQ{
    int x,y,z,w,id;
    bool ok;
    ll mx,val;
    bool operator ==(const QAQ b)const{
        return x==b.x&&y==b.y&&z==b.z&&w==b.w;
    }
}a[N],tmp[N]; 
bool cmp1(QAQ a,QAQ b){
    return a.x==b.x?(a.y==b.y?(a.z==b.z?a.w<b.w:a.z<b.z):a.y<b.y):a.x<b.x;
}
bool cmp2(QAQ a,QAQ b){
    return a.y==b.y?(a.z==b.z?a.w<b.w:a.z<b.z):a.y<b.y;
}
bool cmp3(QAQ a,QAQ b){
    return a.z==b.z?a.w<b.w:a.z<b.z;
}
struct BIT{
    ll bit[N];
    inline int lowbit(int x){
        return x&(-x);
    }
    inline void Add(int x,ll d){
        while(x<=n){
            bit[x]=max(bit[x],d);
            x+=lowbit(x);
        }
    }
    inline ll Ask(int x){
        ll ans=-inf;
        while(x){
            ans=max(ans,bit[x]);
            x-=lowbit(x);
        }
        return ans;
    }
    inline void Clear(int x){
        while(x<=n){
            bit[x]=0;
            x+=lowbit(x);
        }
    }
}B;
void CDQ2(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    CDQ2(l,mid);
    sort(a+l,a+mid+1,cmp3);
    sort(a+mid+1,a+r+1,cmp3);
    int j=l,i=mid+1;
    while(i<=r){
        while(j<=mid&&a[j].z<=a[i].z){
            if(a[j].ok)B.Add(a[j].w,a[j].mx);
            ++j;
        }
        if(!a[i].ok)a[i].mx=max(a[i].mx,B.Ask(a[i].w)+a[i].val);
        ++i;
    }
    for(int i=l;i<j;++i)if(a[i].ok)B.Clear(a[i].w);
    for(int i=l;i<=r;++i)tmp[_pos_2d[a[i].id]]=a[i];
    for(int i=l;i<=r;++i)a[i]=tmp[i];
    CDQ2(mid+1,r);
}
void CDQ1(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    CDQ1(l,mid);
    for(int i=l;i<=mid;++i)a[i].ok=true;
    for(int i=mid+1;i<=r;++i)a[i].ok=false;
    sort(a+l,a+r+1,cmp2);
    for(int i=l;i<=r;++i)_pos_2d[a[i].id]=i;
    CDQ2(l,r);
    for(int i=l;i<=r;++i)tmp[_pos_1d[a[i].id]]=a[i];
    for(int i=l;i<=r;++i)a[i]=tmp[i];
    CDQ1(mid+1,r);
}
int main(){
    n=read();
    for(int i=1;i<=n;++i){
        a[i].x=read(),a[i].y=read(),a[i].z=read(),a[i].w=read(),a[i].val=read();
        b[i]=a[i].w;
    }
    sort(b+1,b+n+1);
    bn=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i){
        a[i].w=lower_bound(b+1,b+bn+1,a[i].w)-b;
    }
    sort(a+1,a+n+1,cmp1);
    int gg=0;
    for(int i=1;i<=n;++i){
        if(a[i]==a[i-1]){
            a[gg].val+=max(0LL,a[i].val);
        }
        else{
            a[++gg]=a[i];
        }
    }
    for(int i=1;i<=n;++i)a[i].mx=a[i].val,a[i].id=i,_pos_1d[a[i].id]=i;
    CDQ1(1,n);
    ans=-inf;
    for(int i=1;i<=n;++i){
        ans=max(ans,a[i].mx); 
    }
    printf("%lld\n",ans);
    return 0;
}

Froggy's blog

呱!!