本蒟蒻第一道(K-D-Tree)维护(dp)
题目大意：求一条路径，使得其四个维度单调不降。
先排序消掉一维再说。
对于每一个点，初始的时候绝对长度是1啊。于是，先赋值一个1，对于每一个点。
设计(dp)数组
[f[i]=max_{f[j]}(a[j]<=a[i],b[j]<=b[i],c[j]<=c[i],d[j]<=d[i])
]
那问题就转为，对于每一个点，如何求出在它之前的最大(f[i])值。
发现问题类似于三维偏序，正好(K-D-Tree)硬刚即可：
对于每一个点，维护这个点的(f[i])值，以及这个点的四个坐标；而树上只需要维护三个维度的上下界以及区间(MAX),动态(query)即可。
（有点懵的是，不能提前处理排序后的第一个点，而必须对所有点一次插入）
(hole:)对于(sort)函数的(cmp)函数，应该以四个维度分别为第(1,2,3,4)关键字排顺序，而不是只排一个。
(Code:)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=5e5+10;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
struct pt{
int x[4],cnt;
}p[MAXN];
#define Alpha 0.75
#define inf 2147483647
struct node{
int mx[3],mi[3],siz,maxn;
pt c;
}tr[MAXN];
int n,m,D,rt,tot,top,ans=-inf;
int ls[MAXN],rs[MAXN],rub[MAXN];
int operator<(pt a,pt b){return a.x[D]<b.x[D];}
inline void pushup(int x){
int l=ls[x],r=rs[x];
tr[x].siz=tr[l].siz+tr[r].siz+1;
for(int i=0;i<=2;++i){
tr[x].mi[i]=tr[x].mx[i]=tr[x].c.x[i];
tr[x].maxn=tr[x].c.cnt;
if(l)tr[x].mi[i]=min(tr[x].mi[i],tr[l].mi[i]),
tr[x].mx[i]=max(tr[x].mx[i],tr[l].mx[i]),
tr[x].maxn=max(tr[x].maxn,tr[l].maxn);
if(r)tr[x].mi[i]=min(tr[x].mi[i],tr[r].mi[i]),
tr[x].mx[i]=max(tr[x].mx[i],tr[r].mx[i]),
tr[x].maxn=max(tr[x].maxn,tr[r].maxn);
}
}
inline bool cmp(pt a,pt b){
return a.x[3]<b.x[3]||(a.x[3]==b.x[3]&&a.x[2]<b.x[2])||(a.x[3]==b.x[3]&&a.x[2]==b.x[2]&&a.x[1]<b.x[1])||(a.x[3]==b.x[3]&&a.x[2]==b.x[2]&&a.x[1]==b.x[1]&&a.x[0]<b.x[0]);
}
inline int New(){
if(top)return rub[top--];
else return ++tot;
}
int build(int l,int r,int d){
if(l>r)return 0;
int x=New(),mid=l+r>>1;
D=d;nth_element(p+l,p+mid,p+r+1);
tr[x].c=p[mid];ls[x]=build(l,mid-1,(d+1)%3);
rs[x]=build(mid+1,r,(d+1)%3);pushup(x);return x;
}
void clear(int x,int pos){
if(ls[x])clear(ls[x],pos);
p[pos+tr[ls[x]].siz+1]=tr[x].c;rub[++top]=x;
if(rs[x])clear(rs[x],pos+tr[ls[x]].siz+1);
}
void check(int &x,int d){
double C=Alpha*(double)(tr[x].siz);
if(C<(double)tr[ls[x]].siz||C<(double)tr[rs[x]].siz){clear(x,0);x=build(1,tr[x].siz,d);}
}
void Ins(int &x,pt s,int d){
if(!x){x=New();ls[x]=rs[x]=0;tr[x].c=s;pushup(x);return;}
if(s.x[d]<=tr[x].c.x[d])Ins(ls[x],s,(d+1)%3);
else Ins(rs[x],s,(d+1)%3);
pushup(x);check(x,d);
}
int f[MAXN];
bool Check(int x,pt s){
int fg=0;
for(int i=0;i<=2;++i){
if(tr[x].mx[i]>s.x[i]){
fg=1;break;
}
}
if(fg)return false;
else return true;
}
bool CK(int x,pt s){
int fg=0;
for(int i=0;i<=2;++i){
if(tr[x].mi[i]>s.x[i])return true;
}
return false;
}
inline bool ck(pt a,pt b){
int fg=1;
for(int i=0;i<=2;++i){
if(a.x[i]>b.x[i]){
fg=0;
break;
}
}
return fg;
}
int query(int x,pt a){
int res=-inf;
if(CK(x,a))return 0;
else if(Check(x,a))return tr[x].maxn;
else {
if(ck(tr[x].c,a))res=max(res,tr[x].c.cnt);
res=max(query(ls[x],a),res);res=max(query(rs[x],a),res);
return res;
}
}
int main(){
n=read();
for(int i=1;i<=n;++i){
p[i].x[0]=read(),p[i].x[1]=read(),p[i].x[2]=read(),p[i].x[3]=read();
}
for(int i=1;i<=n;++i)f[i]=1;
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;++i){
f[i]+=query(rt,p[i]);
// cout<<"当前点f[i]:"<<i<<"<- ->"<<f[i]<<endl;
p[i].cnt=f[i];
Ins(rt,p[i],0);
}
for(int i=1;i<=n;++i)ans=max(ans,f[i]);
printf("%d
",ans);
return 0;
}