四维偏序板子题怎么只有一篇 cdq 题解呢/yiw
首先简单介绍一下 cdq 套 cdq 的思路。我们知道 cdq 的递归树可以理解成一棵线段树。cdq 的过程就是递归到叶子，再回溯回来。而 cdq 套 cdq 的过程则可以如此理解：
-
在第一层递归中到达点 \(x\)。
-
从 \(x\) 进入第二层递归。
-
处理当前贡献。
-
在第二层递归中遍历 \(x\) 的子树。
-
回溯，返回第一层递归。
-
在第一层递归中遍历 \(x\) 的子树。
-
回溯。
并且，cdq 的本质是使若干个 \((0,b,c)\) 的对向 \((1,b,c)\) 做贡献。而在 cdq 套 cdq 中，则变成了 \((0,0,c,d)\) 向 \((1,1,c,d)\)。其中第一维在第一层 cdq 中处理，第二维则在第二层。
到这里，其实读者应该已经可以明白甚至自己解决这个问题了，也可以尝试类似地推导更多层的。然而这题还有许多地方是需要注意的：
-
因为是维护 dp，所以需要类似中序遍历递归树。
-
回溯时要注意还原序列，否则 \([mid+1,r]\) 对应的不是序列实际上的 \([mid+1,r]\)。
-
一定要注意使用稳定排序（stable_sort）或者给每个元素多赋一个关键字！ 否则处理相同元素时会出现问题，建议有重复元素都用这种处理方法。
code：
点击查看代码
int n,m,d[N],tr[N];
struct node{
int a,b,c,d,dp,id;
bool pd;
}e[N],tmp[N];
#define lowbit(x) (x&(-x))
il void update(int x,int y){
while(x<=n){
tr[x]=max(tr[x],y);
x+=lowbit(x);
}
}
il int query(int x){
int ret=0;
while(x){
ret=max(ret,tr[x]);
x-=lowbit(x);
}
return ret;
}
il void init(int x){
while(x<=n){
tr[x]=0;
x+=lowbit(x);
}
}
il bool 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));
}
il bool 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);
}
il bool cmp3(node x,node y){
return x.c!=y.c?x.c<y.c:x.d<y.d;
}
void cdq2(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdq2(l,mid);
stable_sort(e+l,e+mid+1,cmp3),stable_sort(e+mid+1,e+r+1,cmp3);
for(int i=l,j=mid+1;j<=r;j++){
while(i<=mid&&e[i].c<=e[j].c){
if(!e[i].pd)
update(e[i].d,e[i].dp);
i++;
}
if(e[j].pd)
e[j].dp=max(e[j].dp,query(e[j].d)+1);
}
rep(i,l,mid){if(!e[i].pd)init(e[i].d);}
stable_sort(e+l,e+r+1,cmp2);
cdq2(mid+1,r);
}
void cdq1(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdq1(l,mid);
rep(i,l,mid)e[i].pd=false;
rep(i,mid+1,r)e[i].pd=true;
stable_sort(e+l,e+r+1,cmp2);
cdq2(l,r);
stable_sort(e+l,e+r+1,cmp1);
cdq1(mid+1,r);
}
void Yorushika(){
scanf("%d",&n);
rep(i,1,n){
scanf("%d%d%d%d",&e[i].a,&e[i].b,&e[i].c,&e[i].d);
e[i].dp=1,e[i].id=i;
d[i]=e[i].d;
}
stable_sort(d+1,d+n+1),m=unique(d+1,d+n+1)-d-1;
rep(i,1,n){
e[i].d=lower_bound(d+1,d+m+1,e[i].d)-d;
}
stable_sort(e+1,e+n+1,cmp1);
cdq1(1,n);
int ans=0;
rep(i,1,n){
ans=max(ans,e[i].dp);
}
printf("%d\n",ans);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}