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

· · 题解

新增：由于没有考虑负数的影响，被 hack 了，答案的初始值要赋值为负无穷大。

思路：

首先 dp_i 表示以第 i 个点结尾的最长长度，则状态转移方程为：

dp_i=\max([a_j \le a_i][b_j \le b_i][c_j \le c_i][d_j \le d_i] dp_j + w_i)

朴素转移是 O(N^2) 的，一般情况下会超时乱搞能冲过去。

因为这题本质是一个四维偏序问题，可以先将第一维 a 进行排序后，变成了三维空间内求一个长方体内最大点值。

考虑使用数据结构进行维护，开一个三层的树套树，外层是树状数组，中层和下层是动态开点线段树。

这样时间和空间复杂度是 O(N \log^3 N) 的，空间上貌似不允许，考虑 cdq 分治算法。

对于三维偏序问题，先将第一维排序，然后设当前分治区间为 [l,r]，将左右两区间按照第二维排序，现在要计算 [l,mid] 对 [mid+1,r] 的贡献。

明显可以走指针，对于第三维使用树状数组维护即可，时间复杂度为 O(N \log^3 N)，但是空间复杂度基本是 O(N)。

其实 cdq 分治本质上是将左右两区间变成 (a_1,0,c_1) 和 (a_2,1,c_2) 的形式，使得左区间的第二维对于右区间都满足条件。

而四维偏序也是同理，考虑将左右两区间变为 (a_1,0/1,0/1,d_1) 和 (a_2,0/1,0/1,d_2) 的形式。

考虑用 cdq 套 cdq 解决，先变为 (a_1,0,c_1,d_1) 和 (a_2,1,c_2,d_2) 的形式，然后将这个区间的第三维进行 cdq 分治。

时间复杂度为 O(N \log^3 N)。

注意第四维要先离散化。

完整代码：

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
typedef long long ll;
const ll N=50050,INF=1e18; 
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
ll n,cnt,ans=-INF;
ll b[N];
struct Node{
    ll a,b,c,d; 
    ll w,ans;
    bool f;
}a[N];
class BIT{
public:
    ll a[N];
    void add(ll x,ll v){
        for(ll i=x;i<=cnt;i+=lowbit(i))
          a[i]=max(a[i],v);
    }
    void clear(ll x){
        for(int i=x;i<=cnt;i+=lowbit(i))
          a[i]=0;
    }
    ll qurey(ll x){
        ll ans=0;
        for(int i=x;i;i-=lowbit(i))
          ans=max(ans,a[i]);
        return ans;
    }
}T;
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;
    return x.d<y.d;
}
bool cmp3(const Node&x,const Node&y){
    if(x.c!=y.c)
      return x.c<y.c;
    return x.d<y.d;
}
void cdq2(ll l,ll r){
    if(l==r)
      return;
    ll mid=(l+r)>>1;
    cdq2(l,mid);
    stable_sort(a+l,a+mid+1,cmp3);
    stable_sort(a+mid+1,a+r+1,cmp3);
    ll i=l,j=mid+1;
    for(;j<=r;j++){
        while(i<=mid&&a[i].c<=a[j].c){
            if(!a[i].f)
              T.add(a[i].d,a[i].ans);
            i++;
        }
        if(a[j].f)
          a[j].ans=max(a[j].ans,T.qurey(a[j].d)+a[j].w);
    }   
    for(int j=l;j<i;j++)
      if(!a[j].f)
        T.clear(a[j].d);
    stable_sort(a+l,a+r+1,cmp2);
    cdq2(mid+1,r);
}
void cdq1(ll l,ll r){
    if(l==r)
      return;
    ll mid=(l+r)>>1;
    cdq1(l,mid);
    for(int i=l;i<=mid;i++)
      a[i].f=0;
    for(int i=mid+1;i<=r;i++)
      a[i].f=1;
    stable_sort(a+l,a+r+1,cmp2);
    cdq2(l,r);
    stable_sort(a+l,a+r+1,cmp1);
    cdq1(mid+1,r);
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]={read(),read(),read(),read(),read(),-INF,0};
        b[++cnt]=a[i].d;
        a[i].ans=a[i].w;
    }
    stable_sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-(b+1);
    for(int i=1;i<=n;i++)
      a[i].d=lower_bound(b+1,b+cnt+1,a[i].d)-b;
    stable_sort(a+1,a+n+1,cmp1);
    cdq1(1,n);
    for(int i=1;i<=n;i++)
      ans=max(ans,a[i].ans);
    write(ans);
    return 0;
}