题解 P5621 【[DBOI2019]德丽莎世界第一可爱】
Lice
·
·
题解
Description
（简化题意）
给定 n 个四维点，第 i 个点为 (x_i,y_i,z_i,t_i) 。
每个点都带有一个点权，第 i 个点的点权为 w_i。
对于一个合法的路径，满足经过的点的四个坐标全部单调不降。
路径的权定义为该路径所经过点的权值和。
求合法路径权的最大值。
Hint
### Solution
显然可以先按第一维（ $x$ ）升序排序，然后动态规划：
设 $f_i$ 为前 $i$ 个点构成合法路径所能得到路径权的最大值。
状态转移显而易见：
$$f_i = \max\{ f_j | i < j , y_i \ge y_j , z_i\ge z_j , t_i\ge t_j \} + w_i$$
但这样直接做的时间复杂度是 $\Theta(n^2)$ 的，过不了。
我们观察到 状态转移方程中的限制条件 $y_i \ge y_j , z_i\ge z_j , t_i\ge t_j$ 是不是有点像偏序问题？
那么就可以使用 CDQ 分治 或 K-D Tree 了。这里放一个 kdt 的，cdq 这个坑留给之后的题解。
kdt 结点需要存储的信息：
- 左右儿子结点的编号，包含这整个子树的矩形的信息，子树大小（重构用），这个结点代表的三维点（排序已经降低了 1 维），其中点带权。 *这些都是 kdt 维护的常规信息*
- **整个子树中所有点的点权的最大值。**
我们可以把每次更新 $f_i$ 的值，换做 **将第 $i$ 个点，以** $f_i$ **为点权插入到 kdt 中。**
那么还有就是求 $f_i$ 的值。我们在 kdt 中找出所有满足 $y_i \ge y_j , z_i\ge z_j , t_i\ge t_j$ 的 $j$ 然后对其 kdt 中的点权求最值就可以完成了。
在查询时还有一个剪枝技巧，细节详见代码。
### Code
```cpp
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
namespace fastIO_int{
inline long long get_ll()
{
long long x=0;int f=1;char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
x=x*10+c-'0',c=getchar();
return f*x;
}
void read(){}
template<class T1,class ...T2>
void read(T1 &i,T2&... rest)
{
i=get_ll();
read(rest...);
}
void put_ll(long long x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)put_ll(x/10);
putchar(x%10+'0');
}
void write(){}
template<class T1,class ...T2>
void write(T1 i,T2... rest)
{
put_ll(i),putchar(' ');
write(rest...);
}
};
using fastIO_int::read;
using fastIO_int::write;
const int N=5e4+5;
const int K=3;
struct Point{
long long dat[K];
long long val;
};
struct Node{
int ch[2];
long long Max[K],Min[K];
long long maxv;
int size;
Point p;
}t[N];
#define lc(u) t[u].ch[0]
#define rc(u) t[u].ch[1]
int root=0;
int total=0;
stack<int> pool;
inline int create()
{
if(!pool.empty())
{
int ret=pool.top();
return pool.pop(),ret;
}
return ++total;
}
inline void maintain(int u)
{
for(register int i=0;i<K;i++)
{
t[u].Max[i]=t[u].Min[i]=t[u].p.dat[i];
if(lc(u))
{
t[u].Max[i]=max(t[u].Max[i],t[lc(u)].Max[i]);
t[u].Min[i]=min(t[u].Min[i],t[lc(u)].Min[i]);
}
if(rc(u))
{
t[u].Max[i]=max(t[u].Max[i],t[rc(u)].Max[i]);
t[u].Min[i]=min(t[u].Min[i],t[rc(u)].Min[i]);
}
}
t[u].maxv=max(t[u].p.val,max(t[lc(u)].maxv,t[rc(u)].maxv));
t[u].size=t[lc(u)].size+t[rc(u)].size+1;
}
namespace rebuild
{
const double A=0.75;
Point pnt[N];
int dim,len;
bool cmp(const Point &x,const Point &y){
return x.dat[dim]<y.dat[dim];
}
int build(int l,int r,int d)
{
if(l>r) return 0;
int mid=(l+r)>>1,u=create();
dim=d,nth_element(pnt+l,pnt+mid,pnt+r+1,cmp);
t[u].p=pnt[mid];
lc(u)=build(l,mid-1,(d+1)%3);
rc(u)=build(mid+1,r,(d+1)%3);
return maintain(u),u;
}
void travel(int u)
{
if(!u) return;
travel(lc(u));
pnt[++len]=t[u].p;
pool.push(u);
travel(rc(u));
}
bool balance(int u)
{
if(double(t[lc(u)].size)>=A*double(t[u].size)) return 0;
if(double(t[rc(u)].size)>=A*double(t[u].size)) return 0;
return 1;
}
void work(int &u,int d)
{
if(balance(u)) return;
len=0,travel(u);
u=build(1,len,d);
}
}
void insert(Point p,int &u=root,int d=0)
{
if(!u)
{
t[u=create()].p=p;
return maintain(u);
}
if(p.dat[d]<=t[u].p.dat[d]) insert(p,lc(u),(d+1)%3);
else insert(p,rc(u),(d+1)%3);
maintain(u),rebuild::work(u,d);
}
bool inside(Point p,int u)
{
for(register int i=0;i<K;i++)
if(p.dat[i]<t[u].Max[i]) return 0;
return 1;
}
bool outside(Point p,int u)
{
for(register int i=0;i<K;i++)
if(p.dat[i]<t[u].Min[i]) return 1;
return 0;
}
bool check_in(Point p,Point q)
{
for(register int i=0;i<K;i++)
if(p.dat[i]<q.dat[i]) return 0;
return 1;
}
void query(Point p,long long &ret,int u=root)
{
if(!u||outside(p,u)) return;
if(ret>=t[u].maxv) return;//剪枝：如果找过的答案已经不小于这个子树的点权最大值，那么这个子树也不可能对答案产生贡献，故直接 return。
if(inside(p,u)) return void(ret=max(ret,t[u].maxv));
if(check_in(p,t[u].p)) ret=max(ret,t[u].p.val);
query(p,ret,lc(u)),query(p,ret,rc(u));
}
#undef lc
#undef rc
struct Item{
long long H,rec;
Point p;
void read_data(){
read(H);
for(register int i=0;i<K;i++)
read(p.dat[i]);
read(rec);
}
bool operator <(const Item &t)const{
if(H!=t.H) return H<t.H;
for(register int i=0;i<K;i++)
{
if(p.dat[i]<t.p.dat[i]) return true;
if(p.dat[i]>t.p.dat[i]) return false;
}
return false;
}
}itm[N];
int n;
signed main()
{
read(n);
for(register int i=1;i<=n;i++)
itm[i].read_data();
sort(itm+1,itm+1+n);
long long ans=0ll;
for(register int i=1;i<=n;i++)
{
long long temp=0;
query(itm[i].p,temp);
temp+=itm[i].rec;
ans=max(ans,temp);
itm[i].p.val=temp;
insert(itm[i].p);
}
write(ans);
return 0;
}
```
如果您还觉得慢的话，这里还有一个优化技巧：
我们不妨将整棵树建好（就这 $n$ 个点，没跑），初始所有点权为 $0$ ，插入操作则以 **修改** 代替。这样既不会导致树不平衡，也不需要任何重构了。
~~代码 spfa 了~~ 这个应该可以自己写出来。
求赞 QwQ。