德丽傻可爱可爱！

· · 题解

刚从 P4849 出来就看到这道题，发现本题只是去掉了求方案数的操作，甚至改了改 IO 格式就过了。

记 h 为 health，e 为 energy，a 为 attack，d 为 defence，c 为 collapse。

考虑 dp，状态为 dp_i，表示第 i 只崩坏兽被干掉时能够获得的最大可爱值，那么有状态转移方程：

dp_i=c_i+\max\limits_{h_j\le h_i,e_j\le h_i,a_j\le a_i,d_j\le d_i} dp_j

直接转移肯定是 O(n^2) 的。由于转移存在四维偏序关系，那么可以用 CDQ 套 CDQ 的做法来优化至 O(n\log^3n)。

具体做法与三维偏序类似：排序处理第一维，外层 CDQ 处理第二维，内层 CDQ 处理第三维，BIT 处理第四维。不过有一些需要注意的点：

从 P4849 改的 AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define _r return*this
#define _o &operator
namespace IO
{
    const int _S=1<<21;
    char b[_S],*p1=b,*p2=b,pb[_S],*pp=pb;
    void fl(){fwrite(pb,1,pp-pb,stdout),pp=pb;}
    struct input
    {
        char gc(){if(p1==p2)p2=(p1=b)+fread(b,1,_S,stdin);return p1==p2?' ':*p1++;}
        input _o>>(char&num){do num=gc();while(num==' '||num=='\n'||num=='\r'||num=='\t');_r;}
        template<typename T>input _o>>(T&x)
        {
            char c=gc();T f=1;
            for(x=0;!isdigit(c);)(c=='-'?f=-1:1),c=gc();
            while(isdigit(c))x=(x*10)+(c^48),c=gc();
            x*=f;_r;
        }
        input(){}
    }in;
    struct output
    {
        void pt(char num){*pp++=num;if(pp-pb==_S)fl();}
        output _o<<(char num){pt(num);_r;}
        template<typename T>output _o<<(T x)
        {
            if(!x){pt(48);_r;}
            if(x<0)pt('-'),x=-x;
            int s[64],t=0;
            while(x)s[++t]=x%10,x/=10;
            while(t)pt(s[t--]+48);
            _r;
        }
        output _o<<(const char*s){int num=0;while(s[num])pt(s[num++]);_r;}
        output(){}
    }out;
    struct fe{~fe(){fl();}}fls;
}
using IO::in;
using IO::out;
using ll=long long;

#define N 80001
#define MOD 998244353

struct ANS
{
    ll mx,tot;
    void upd(ANS B)
    {
        if(B.mx>mx)*this=B;
        else if(B.mx==mx)(tot+=B.tot)%=MOD;
    }
}ans;

struct node
{
    ll i,a,b,c,d,v;
    bool f1,f2;
    ANS s;
    bool operator==(node o){return a==o.a&&b==o.b&&c==o.c&&d==o.d;}
}A[N],B[N],C[N];
bool cmp1(const node&x,const node&y)
{
    if(x.a!=y.a)return x.a<y.a;
    if(x.b!=y.b)return x.b<y.b;
    if(x.c!=y.c)return x.c<y.c;
    return x.d<y.d;
}
bool cmp2(const node&x,const node&y)
{
    if(x.b!=y.b)return x.b<y.b;
    if(x.c!=y.c)return x.c<y.c;
    if(x.d!=y.d)return x.d<y.d;
    return x.a<y.a;
};
bool cmp3(const node&x,const node&y)
{
    if(x.c!=y.c)return x.c<y.c;
    if(x.d!=y.d)return x.d<y.d;
    if(x.a!=y.a)return x.a<y.a;
    return x.b<y.b;
};

ll n;

ll tmp[N];
void init()
{
    sort(A+1,A+1+n,cmp1);
    for(int i=2,j=1;i<=n;i++)
    {
        if(A[i]==A[j])A[j].v+=A[i].v;
        else A[++j]=A[i];
        if(i==n)n=j;
    }

    for(int i=1;i<=n;i++)tmp[i]=A[i].a;
    sort(tmp+1,tmp+1+n);
    for(int i=1,j=unique(tmp+1,tmp+1+n)-tmp-1;i<=n;i++)
        A[i].a=lower_bound(tmp+1,tmp+1+j,A[i].a)-tmp;


    for(int i=1;i<=n;i++)tmp[i]=A[i].b;
    sort(tmp+1,tmp+1+n);
    for(int i=1,j=unique(tmp+1,tmp+1+n)-tmp-1;i<=n;i++)
        A[i].b=lower_bound(tmp+1,tmp+1+j,A[i].b)-tmp;

    for(int i=1;i<=n;i++)tmp[i]=A[i].c;
    sort(tmp+1,tmp+1+n);
    for(int i=1,j=unique(tmp+1,tmp+1+n)-tmp-1;i<=n;i++)
        A[i].c=lower_bound(tmp+1,tmp+1+j,A[i].c)-tmp;

    for(int i=1;i<=n;i++)tmp[i]=A[i].d;
    sort(tmp+1,tmp+1+n);
    for(int i=1,j=unique(tmp+1,tmp+1+n)-tmp-1;i<=n;i++)
        A[i].d=lower_bound(tmp+1,tmp+1+j,A[i].d)-tmp;

    for(int i=1;i<=n;i++)A[i].i=i,A[i].s={A[i].v,1};
}

struct BIT
{
#define lowbit(x) x&-x
    ANS C[N];
    void D(ll p){while(p<=n)C[p]={0,0},p+=lowbit(p);}
    void A(ll p,ANS x){while(p<=n)C[p].upd(x),p+=lowbit(p);}
    void Q(ll p,ANS&x,ll v){while(p)x.upd({C[p].mx+v,C[p].tot}),p-=lowbit(p);}
}T;

#define mid ((l+r)>>1)
void CDQ2(ll l,ll r)
{
    if(l==r)return;
    CDQ2(l,mid);
    for(int i=l;i<=r;i++)B[i].f2=(i>mid),C[i]=B[i],C[i].i=i;
    sort(C+l,C+1+r,cmp3);
    for(int i=l;i<=r;i++)
        if(C[i].f1&&C[i].f2)
            T.Q(C[i].d,C[i].s,C[i].v),B[C[i].i].s=C[i].s;
    else if(!C[i].f1&&!C[i].f2)T.A(C[i].d,C[i].s);
    for(int i=l;i<=mid;i++)if(!B[i].f1)T.D(B[i].d);
    CDQ2(mid+1,r);
}
void CDQ1(ll l,ll r)
{
    if(l==r)return;
    CDQ1(l,mid);
    for(int i=l;i<=r;i++)A[i].f1=(i>mid),B[i]=A[i],B[i].i=i;
    sort(B+l,B+1+r,cmp2),CDQ2(l,r);
    for(int i=l;i<=r;i++)A[B[i].i].s=B[i].s;
    CDQ1(mid+1,r);
}

bool nega=true;
ll mx=numeric_limits<ll>::min();
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>A[i].a>>A[i].b>>A[i].c>>A[i].d>>A[i].v,nega&=(A[i].v<0),mx=max(mx,A[i].v);
    if(nega)return out<<mx,0;
    init(),CDQ1(1,n);
    for(int i=1;i<=n;i++)ans.upd(A[i].s);
    out<<ans.mx;
}