题解 P4849 【寻找宝藏】
绝顶我为峰
2021-01-07 22:40:07
## Problem
四维空间，每次可以在每个维度向正半轴移动一个单位，可以获得途经的所有点的贡献。求从 $(1,1,1,1)$ 到 $(m,m,m,m)$ 的所有路径中的最大贡献，并求出方案数。
## Solution
首先有一个非常 naive 的 dp 做法，对于每个可以转移的点对连一条有向边，最后在 DAG 上 dp。
这种做法是 $O(n^2)$ 的，显然无法通过。
考虑优化这个 dp，我们注意到一个点对另一个点可以产生贡献，当且仅当二者满足偏序关系。
这是一个裸的四维偏序，用 CDQ 优化 dp 即可。
~~众所周知~~高维偏序每套一层 CDQ 就可以用一个 log 的复杂度降掉一维，于是我们有了一个 CDQ 套 CDQ 的做法，复杂度 $O(nlog^3n)$，可以通过本题。
默认大家已经会了 CDQ。三维偏序大家都会，这里讲一下怎样实现四维偏序（这个做法也适用于更高维的偏序）。
我们考虑一个序列，第一维有序，那么对于一个区间 $[l,r]$，考虑计算 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。
由于第一维有序，$[l,mid]$ 第一维一定小于 $[mid+1,r]$ 第一维，那么我们直接给两段序列打上标记（我把左半段标记为 1，右半段标记为 0），删去这一维即可。
接下来就是普通的三维偏序了，唯一的区别在于扫描区间时只有左指针指向标记是 1 的点时才加入数据结构，右指针指向标记是 0 的点时才计算贡献。
数据结构需要维护最大值和对应的方案数，类似[[SDOI2011]拦截导弹](https://www.luogu.com.cn/problem/P2487)，最后统计所有答案等于最大值的点的方案数只和即可。
注意一个点可能有多个贡献，要先去重。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long mod=998244353;
long long n,m,p[80001],cnt,ans[80001],val[80001],sum,tot;
pair<long long,long long> dp[80001];
struct element
{
long long x,y,z,w,id,val,cnt;
bool tag;
bool operator ==(const element &other) const
{
return x==other.x&&y==other.y&&z==other.z&&w==other.w;
}
}a[80001],b[80001],c[80001];
inline bool cmp1(element x,element y)
{
return x.x^y.x? x.x<y.x:x.y^y.y? x.y<y.y:x.z^y.z? x.z<y.z:x.w<y.w;
}
inline bool cmp2(element x,element y)
{
return x.y^y.y? x.y<y.y:x.z^y.z? x.z<y.z:x.w^y.w? x.w<y.w:x.x<y.x;
}
inline bool cmp3(element x,element y)
{
return x.z^y.z? x.z<y.z:x.w^y.w? x.w<y.w:x.x^y.x? x.x<y.x:x.y<y.y;
}
inline long long read()
{
long long x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
inline int lowbit(int x)
{
return x&-x;
}
inline void update(int k,long long p,long long v)
{
v%=mod;
for(;k<=cnt;k+=lowbit(k))
{
if(ans[k]==p)
val[k]=(val[k]+v)%mod;
if(p>ans[k])
{
ans[k]=p;
val[k]=v;
}
}
}
inline pair<long long,long long> query(int k)
{
pair<long long,long long> res=make_pair(0,0);
for(;k;k-=lowbit(k))
{
if(ans[k]==res.first)
res.second=(res.second+val[k])%mod;
if(ans[k]>res.first)
{
res.first=ans[k];
res.second=val[k];
}
}
return res;
}
inline void clear(int k)
{
for(;k<=cnt;k+=lowbit(k))
ans[k]=val[k]=0;
}
void cdq2(int l,int r)
{
if(l==r)
return;
int mid=(l+r)>>1;
cdq2(l,mid);
for(register int i=l;i<=r;++i)
c[i]=b[i];
sort(c+l,c+mid+1,cmp3);
sort(c+mid+1,c+r+1,cmp3);
int i=l,j=mid+1;
while(j<=r)
{
if(c[j].tag)
{
++j;
continue;
}
while(i<=mid&&c[i].z<=c[j].z)
{
if(c[i].tag)
update(c[i].w,dp[c[i].id].first,dp[c[i].id].second);
++i;
}
pair<long long,long long> tmp=query(c[j].w);
tmp.first+=c[j].val;
if(tmp.first==dp[c[j].id].first)
dp[c[j].id].second=(dp[c[j].id].second+tmp.second)%mod;
if(tmp.first>dp[c[j].id].first)
dp[c[j].id]=tmp;
sum=max(sum,dp[c[j].id].first);
++j;
}
for(register int t=l;t<i;++t)
if(c[t].tag)
clear(c[t].w);
cdq2(mid+1,r);
}
void cdq1(int l,int r)
{
if(l==r)
return;
int mid=(l+r)>>1;
cdq1(l,mid);
for(register int i=l;i<=r;++i)
b[i]=a[i];
for(register int i=l;i<=mid;++i)
b[i].tag=1;
sort(b+l,b+r+1,cmp2);
cdq2(l,r);
cdq1(mid+1,r);
}
int main()
{
n=read(),m=read();
for(register 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();
p[i]=a[i].w;
}
sort(p+1,p+n+1);
cnt=unique(p+1,p+n+1)-p-1;
for(register int i=1;i<=n;++i)
a[i].w=lower_bound(p+1,p+cnt+1,a[i].w)-p;
sort(a+1,a+n+1,cmp1);
tot=1;
for(register int i=2;i<=n;++i)
if(a[i]==a[tot])
a[tot].val+=a[i].val;
else
a[++tot]=a[i];
n=tot;
tot=0;
for(register int i=1;i<=n;++i)
{
a[i].id=i;
dp[i].first=a[i].val;
dp[i].second=1;
}
cdq1(1,n);
printf("%lld\n",sum);
for(register int i=1;i<=n;++i)
if(dp[i].first==sum)
tot=(tot+dp[i].second)%mod;
printf("%lld\n",tot);
return 0;
}
```