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

· · 题解

题意

求四维权值最大不降链。

可以很快想到一个 O(n^2) 的做法，那就是对于每个数按第一维排序，然后暴力找到合法前缀最大值，更新这个数的答案。

那么实际上就是个三维偏序问题。

解法

考虑分块，将序列按第一维排序后分块，块长为 B。

先假设我们已经有了对于现在块内每个数在前面的块中的最大合法答案，那么只需要把这个答案和块内前面的合法点一一比较即可，时间复杂度 O(nB)。

考虑怎么求这个答案。

可以对所有数先离散化一边，然后把答案对应到该三维点上，再求一遍三维前缀最大值，但这样的时间复杂度是 O(\dfrac{n^4}{B})， 明显过不了。

实际上，我们要求的只是对这个块内点的答案，所以完全不需要每次对整个值域做上述操作。

所以我们可以把所有数按该块内的数进行离散化，这样子不影响它们之间的相对大小，也就不影响答案，但要做的问题规模变成了 B。

于是就可以在 O(\dfrac{n}{B}(B^3+n)) 的时间内求出来块内每个数在前面的块中的最大合法答案。

总时间复杂度为 O(nB+\dfrac{n}{B}(B^3+n))， 在 B 为 \sqrt[3]{n} 时为最优，空间线性。

代码

#include<bits/stdc++.h>
using namespace std;
inline long long qread()
{
    register long long a=0,f=1;register char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){(a*=10)+=(ch^48);ch=getchar();}
    return a*f;
}
int n,cl,c[50010],st[50010],ed[50010],que[3][50010],en[3],tot;
int xx,yy,zz,cc[3][200010],p[3];
long long ans[50010],mp[100][100][100],b[200010];
struct poin
{
    int a,b,c,d;
    long long v;
}a[50010];
inline bool cmp(register poin x,register poin y){return x.a==y.a?(x.b==y.b?(x.c==y.c?x.d<y.d:x.c<y.c):x.b<y.b):x.a<y.a;}
inline long long find(register int x,register int y,register int z)
{
    long long an=0;
    an=max(an,mp[x-1][y][z]);
    an=max(an,mp[x][y-1][z]);
    an=max(an,mp[x][y][z-1]);
    return an;
} 
inline bool check(register int x,register int y)
{
    if(a[x].b>a[y].b)return 0;
    if(a[x].c>a[y].c)return 0;
    if(a[x].d>a[y].d)return 0;
    return 1;
}
int main()
{
    n=qread();
    cl=pow(n,0.333333)+1;
    for(register int i=1;i<=n;++i)b[++tot]=a[i].a=qread(),b[++tot]=a[i].b=qread(),b[++tot]=a[i].c=qread(),b[++tot]=a[i].d=qread(),a[i].v=qread(),c[i]=(i-1)/cl+1,ed[c[i]]=i;
    sort(b+1,b+1+tot);
    tot=unique(b+1,b+1+tot)-b-1;
    for(register int i=1;i<=n;++i)
    {
        a[i].a=lower_bound(b+1,b+1+tot,a[i].a)-b;
        a[i].b=lower_bound(b+1,b+1+tot,a[i].b)-b;
        a[i].c=lower_bound(b+1,b+1+tot,a[i].c)-b;
        a[i].d=lower_bound(b+1,b+1+tot,a[i].d)-b;
    }
    for(register int i=n;i;--i)st[c[i]]=i;
    sort(a+1,a+1+n,cmp);
    for(register int i=1;i<=c[n];++i)
    {
        en[0]=en[1]=en[2]=0;
        for(register int j=st[i];j<=ed[i];++j)
        {
            que[0][++en[0]]=a[j].b;
            que[1][++en[1]]=a[j].c;
            que[2][++en[2]]=a[j].d;
        }
        sort(que[0],que[0]+en[0]+1);
        sort(que[1],que[1]+en[1]+1);
        sort(que[2],que[2]+en[2]+1);
        en[0]=unique(que[0],que[0]+en[0]+1)-que[0]-1;
        en[1]=unique(que[1],que[1]+en[1]+1)-que[1]-1;
        en[2]=unique(que[2],que[2]+en[2]+1)-que[2]-1;
        p[0]=p[1]=p[2]=0;
        for(register int j=1;j<=n*4;++j)
        {
            while(que[0][p[0]]<j&&p[0]<=en[0])++p[0];
            while(que[1][p[1]]<j&&p[1]<=en[1])++p[1];
            while(que[2][p[2]]<j&&p[2]<=en[2])++p[2];
            cc[0][j]=p[0],cc[1][j]=p[1],cc[2][j]=p[2];
        }
        for(register int j=1;j<st[i];++j)
        {
            xx=cc[0][a[j].b];
            yy=cc[1][a[j].c];
            zz=cc[2][a[j].d];
            mp[xx][yy][zz]=max(mp[xx][yy][zz],ans[j]);
        }
        for(register int j=1;j<=en[0];++j)
        {
            for(register int k=1;k<=en[1];++k)
            {
                for(register int l=1;l<=en[2];++l)
                {
                    mp[j][k][l]=max(mp[j][k][l],find(j,k,l));
                }
            }
        }
        for(register int j=st[i];j<=ed[i];++j)
        {
            xx=cc[0][a[j].b];
            yy=cc[1][a[j].c];
            zz=cc[2][a[j].d];
            ans[j]=mp[xx][yy][zz]+a[j].v;
            for(register int k=st[i];k<j;++k)if(check(k,j))ans[j]=max(ans[j],ans[k]+a[j].v);
        }
        for(register int j=1;j<=en[0]+1;++j)
        {
            for(register int k=1;k<=en[1]+1;++k)
            {
                for(register int l=1;l<=en[2]+1;++l)
                {
                    mp[j][k][l]=0;
                }
            }
        }
    }
    for(register int i=1;i<=n;++i)ans[0]=max(ans[0],ans[i]);
    printf("%lld",ans[0]);
    return 0;
}