自动搬运

查看原文

来自洛谷，原作者为

	Wind_Leaves_ShaDow 别摆了。

搬运于2025-08-24 22:12:39，当前版本为作者最后更新于2024-03-30 11:14:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

cdq 套 cdq 的板子。（？）

如果您是像我一样初学 cdq 的初学者，那么这篇博客 可能 带给您：

• 本题的 AC 代码、思路以及基本原理相同的 双倍经验。

• 用 cdq 优化 dp 时为何需注意分治顺序，以及将顺序更改后同时需改变哪些部分。

• 可能 的复杂度证明。

因为作者是蒟蒻，只能尽自己所能将对 cdq 的理解写下来供参考，若有疑问、质疑或不满请私聊或移步至其他题解。

令 $dp_i$ 表示以 $i$ 为终点最多能获得多大可爱值。

有 $dp_{i}=dp_j+c_i$，其中 $j$ 是满足 $h_j\le h_i,e_j\le e_i,a_j\le a_i,d_j\le d_i$ 的 $j$ 中 $dp_j$ 最大的一个。

直接枚举复杂度是 $O(n^2)$ 的。

考虑三维偏序是 cdq，那么四维偏序也能 cdq。

cdq 的本质就是处理左区间对右区间的贡献。

那么在第一层 cdq 里面我们对一个 $i$ 定义一个 $lf_i$ 表示它是给贡献的点还是被贡献的点。这样我们就能带着这一层的状态进到下一个 cdq 里面，然后就变成了普通的三维偏序。

对于第四维的树状数组，我们看第二层被判断为给贡献的点在第一层是不是也是给贡献的，只有当两个都能满足的时候才能代表这个点能更新后面的其他点。

离散化去重都是很常见的操作不讲了。

然后是 cdq 更新 dp 的顺序。

正常的暴力 dp 需要保证什么？

对于任意一个 $i$，所有能更新它的点 $j$ 都已经被更新过了。

否则就会出现我先把 $i$ 用 $j$ 更新，然后我把 $j$ 更新导致 $i$ 没有被更新到。

所以我们在 cdq 里面也要这样子，把左区间更新完后直接处理贡献再看右区间。

有一个小问题，我们在处理贡献时将左右区间按第三维排序，此时打乱了原先按第二维排序的顺序。

右区间的顺序被打乱了，原先往下走应该是按照第二维排序才能得到内层 cdq 的左右区间，但是现在得到的左右区间是基于第三维排序得到的。

解决方法有两个，一个是把按照第二维排序的数组拷贝一个新的然后用那个新的来处理贡献，另一个是在每次内层 cdq 开始时重新按第二维排序。

然后是复杂度。

三维偏序我们考虑每一个点都会被访问 $\log n$ 次，一共 $n$ 个点，乘上树状数组的 $\log n$，所以就是 $O(n\log^2 n)$。

对于四维偏序，我们考虑每一个点会被访问的次数。在外围 cdq 会是 $\log n$ 次，每一次又会在内层访问大致 $\log n$ 次，所以总访问次数是 $\log^2 n$ 的，其他的复杂度一样，所以总复杂度是 $O(n\log^3 n)$ 次。

喜闻乐见的 代码：

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))

using namespace std;
const int N=2e5,Inf=1e18;

inline int read(){
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}

inline void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return;
}

int cdn,n=0,dp[N+5],gs[N+5],ans=-Inf;
int lsh[(N<<2)+5],m=0;

inline void cmx(int p,int x){
	for(;p<=m;p+=lowbit(p))gs[p]=max(gs[p],x);
	return;
}

inline int gmx(int p){
	int ret=-Inf;
	for(;p;p-=lowbit(p))ret=max(ret,gs[p]);
	return ret;
}

inline void cgs(int p){
	for(;p<=m;p+=lowbit(p))gs[p]=-Inf;
	return;
}

struct Node{
	int h,e,a,d,c,id;
	bool lf;
}a[N+5],b[N+5],c1[N+5],c2[N+5];

inline void Disc(){
	for(int i=1;i<=cdn;i++){
		lsh[++m]=a[i].h;
		lsh[++m]=a[i].e;
		lsh[++m]=a[i].a;
		lsh[++m]=a[i].d; 
	}
	sort(lsh+1,lsh+m+1);
	m=unique(lsh+1,lsh+m+1)-lsh-1;
	for(int i=1;i<=cdn;i++){
		a[i].h=lower_bound(lsh+1,lsh+m+1,a[i].h)-lsh;
		a[i].e=lower_bound(lsh+1,lsh+m+1,a[i].e)-lsh;
		a[i].a=lower_bound(lsh+1,lsh+m+1,a[i].a)-lsh;
		a[i].d=lower_bound(lsh+1,lsh+m+1,a[i].d)-lsh;
	}
	return;
} 

inline bool cmp1(Node x,Node y){
	return (x.h^y.h?x.h<y.h:(x.e^y.e?x.e<y.e:(x.a^y.a?x.a<y.a:(x.d^y.d?x.d<y.d:x.c>y.c))));
}

inline bool cmp2(Node x,Node y){
	return (x.e^y.e?x.e<y.e:(x.a^y.a?x.a<y.a:(x.d^y.d?x.d<y.d:x.h<y.h)));
}

inline bool cmp3(Node x,Node y){
	return (x.a^y.a?x.a<y.a:(x.d^y.d?x.d<y.d:(x.h^y.h?x.h<y.h:x.e<y.e)));
}

inline void cdq2(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1,pl=l,pr=mid+1;
	cdq2(l,mid);
	for(int i=l;i<=r;i++)c1[i]=c2[i];
	sort(c1+pl,c1+mid+1,cmp3);
	sort(c1+pr,c1+r+1,cmp3);
	while(pl<=mid&&pr<=r){
		if(c1[pl].a<=c1[pr].a){
			if(c1[pl].lf)cmx(c1[pl].d,dp[c1[pl].id]);
			pl++;
		}else{
			if(!c1[pr].lf)dp[c1[pr].id]=max(dp[c1[pr].id],gmx(c1[pr].d)+c1[pr].c);
			pr++;
		}
	}
	for(;pr<=r;pr++)if(!c1[pr].lf)dp[c1[pr].id]=max(dp[c1[pr].id],gmx(c1[pr].d)+c1[pr].c);
	for(int i=l;i<pl;i++)if(c1[i].lf)cgs(c1[i].d);
	cdq2(mid+1,r);
	return;
}

inline void cdq1(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq1(l,mid);
	for(int i=l;i<=r;i++){
		c2[i]=b[i];
		c2[i].lf=(i<=mid);
	}
	sort(c2+l,c2+r+1,cmp2);
	cdq2(l,r);
	cdq1(mid+1,r);
	return;
}

signed main(){
	cdn=read();
	for(int i=1;i<=cdn;i++){
		a[i]={read(),read(),read(),read(),read(),0,0};
		ans=max(ans,a[i].c);//有 c 全部是负的数据。
	}
	Disc();
	sort(a+1,a+cdn+1,cmp1);
	for(int i=1;i<=cdn;i++){
		if((a[i].h^b[n].h)||(a[i].e^b[n].e)||(a[i].a^b[n].a)||(a[i].d^b[n].d))b[++n]=a[i];
		else if(a[i].c>0)b[n].c+=a[i].c;
	}
	for(int i=1;i<=n;i++){
		dp[i]=b[i].c;
		b[i].id=i;
	} 
	for(int i=1;i<=m;i++)gs[i]=-Inf;
	cdq1(1,n);
	for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
	write(ans);
	return 0;
}

写的很长很丑，题解也很长很丑，不喜勿喷，谢谢。