P5621 [DBOI2019]德丽莎世界第一可爱（题解）
Update.
az，听说被 Hack 了？
我当时写 CDQ 时 Too Young，修改了一下 cmp 函数 qwq。
Background
你正在打《Summer Pockets Reflection Blue》，突然家长进来了，于是你装作在写题解。
来帮 _Wallace_ 补 CDQ 的题解了qwq。
Description.
每个节点有五个性质。具体是什么只有打过崩环的人才知道，反正我是不知道。
现在你需要找出前四个数值都严格不降的序列。（可以不按照原序列顺序。
使这个序列权值最大。（一个序列的权值定义为这个序列中所有元素的第五个权值之和，可能为负。
（序列不能为空。
P.S.
前置知识：CDQ 分支解决三维偏序。
Solution.
四维偏序板子，这篇题解的做法是 CDQ 套 CDQ。
我们首先考虑 CDQ 的本质是什么（笔者个人理解。
本质就是找到一条分界线，然后左边向右边贡献。
然后左边向右边的贡献又可以排序+树状数组求出。
这样就有三维了，其实第一维是隐藏在归并排序（分界线）中的。
那么对于四维偏序，我们只需要用两个归并排序（CDQ）就好了。
而这个分界线的本质意义就是把当前区间的所有点分成两类。
一类是贡献点，一类是被贡献点，然后直接贡献点向被贡献点转移就好了。
复杂度
如果看不懂可以参考代码及其注释。
Coding.
//愿你和你重要的人能够重逢！
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:0;
}//注意开long long
struct node{int a,b,c,d,id;char ck;ll mx,vl;}a[50005],tmp[50005];
inline char operator==(node x,node y) {return x.a==y.a&&x.b==y.b&&x.c==y.c&&x.d==y.d;}
inline char cmp1(node x,node y) {return x.a^y.a?x.a<y.a:(x.b^y.b?x.b<y.b:(x.c^y.c?x.c<y.c:x.d<y.d));}
inline char cmp2(node x,node y) {return x.b^y.b?x.b<y.b:(x.c^y.c?x.c<y.c:(x.d^y.d?x.d<y.d:x.a<y.a));}
inline char cmp3(node x,node y) {return x.c^y.c?x.c<y.c:(x.d^y.d?x.d<y.d:(x.a^y.a?x.a<y.a:x.b<y.b));}
//上面是结构体。
int n,id1[50005],id2[50005],tn[50005],ut;ll T[50005];
inline void upd(int x,ll w) {for(;x<=ut;x+=x&(-x)) if(T[x]<w) T[x]=w;else return;}
inline void clr(int x) {for(;x<=ut;x+=x&(-x)) if(T[x]) T[x]=0;else return;}
inline ll qry(int x) {ll r=0;for(;x;x-=x&(-x)) r=max(r,T[x]);return r;}
//上面是树状数组模板
inline void cdq1(int l,int r)
{//这是第一个 CDQ，ck 是区分贡献点（1）和被贡献点（0）的。
int md,i,j;if(l==r) return;else md=(l+r)>>1,cdq1(l,md);
sort(a+l,a+md+1,cmp3),sort(a+md+1,a+r+1,cmp3),j=l,i=md+1;
// for(int i=l;i<=r;i++) printf("%d%c",a[i].id,i==r?'\n':' ');
// for(int i=l;i<=r;i++) printf("%lld%c",a[i].mx,i==r?'\n':' ');
//归并排序
while(i<=r&&j<=md)
if(a[j].c<=a[i].c) {if(a[j].ck) upd(a[j].d,a[j].mx);j++;}
else {if(!a[i].ck) a[i].mx=max(a[i].mx,qry(a[i].d)+a[i].vl);i++;}
while(i<=r) {if(!a[i].ck) a[i].mx=max(a[i].mx,qry(a[i].d)+a[i].vl);i++;}
for(int k=l;k<j;k++) if(a[k].ck) clr(a[k].d);
for(int i=l;i<=r;i++) tmp[id2[a[i].id]]=a[i];
// for(int i=l;i<=r;i++) printf("%lld%c",a[i].mx,i==r?'\n':' ');
{for(int i=l;i<=r;i++) a[i]=tmp[i];}cdq1(md+1,r);
}
inline void cdq(int l,int r)
{//大CDQ
int md;if(l==r) return;else md=(l+r)>>1,cdq(l,md);
for(int i=l;i<=r;i++) a[i].ck=(i<=md);
sort(a+l,a+r+1,cmp2);for(int i=l;i<=r;i++) id2[a[i].id]=i;
cdq1(l,r);for(int i=l;i<=r;i++) tmp[id1[a[i].id]]=a[i];
{for(int i=l;i<=r;i++) a[i]=tmp[i];}cdq(md+1,r);
}
int main()
{
/*freopen("in.txt","r",stdin);*/read(n);
for(int i=1;i<=n;i++) read(a[i].a),read(a[i].b),read(a[i].c),read(a[i].d),read(a[i].vl),tn[i]=a[i].d;
sort(tn+1,tn+n+1),ut=unique(tn+1,tn+n+1)-tn-1,sort(a+1,a+n+1,cmp1);//注意离散化
for(int i=1;i<=n;i++) a[i].d=lower_bound(tn+1,tn+ut+1,a[i].d)-tn;
int cn=0;for(int i=1;i<=n;i++) if(a[i]==a[i-1]) a[cn].vl+=max(a[i].vl,0ll);else a[++cn]=a[i];
n=cn;for(int i=1;i<=n;i++) a[i].mx=a[i].vl,a[i].id=id1[i]=i;
// for(int i=1;i<=n;i++) printf("%d %d %d %d %lld %lld\n",a[i].a,a[i].b,a[i].c,a[i].d,a[i].vl,a[i].mx);
cdq(1,n);ll rs=-1e18;for(int i=1;i<=n;i++) rs=max(rs,a[i].mx);
return printf("%lld\n",rs),0;//然后就没了qwq
}