TATT
题意：
求最长的非递减的四维偏序长度。
思路：
先将序列任选一个维度进行排序，然后依次将这些点插入到K-D Tree中。每插入一个点之前，计算以当前点结尾的最长偏序长度（剩下的是三维偏序问题），然后再将当前点插入即可。当然，K-D Tree重点还是在剪枝上。此处考虑两种剪枝即可：
如果当前子空间某一个维度的最下值都大于询问点的这一维度，则剪枝；如果当前子空间最长偏序长度小于当前答案值，则剪枝（询问时优先处理可能的长度较长的子空间）。
代码
#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std
;
typedef long long ll
;
typedef pair
<int,int> pr
;
inline int read() {int x
=0,f
=1;char c
=getchar();while(c
!='-'&&(c
<'0'||c
>'9'))c
=getchar();if(c
=='-')f
=-1,c
=getchar();while(c
>='0'&&c
<='9')x
=x
*10+c
-'0',c
=getchar();return f
*x
;}
const int maxn
= 5e4+10;
const int inf
= 0x3f3f3f3f;
const int mod
= 1e9+7;
const double eps
= 1e-7;
int n
, Dim
, tot
, rt
, top
;
int ls
[maxn
], rs
[maxn
], sz
[maxn
], mi
[maxn
][3], mx
[maxn
], rub
[maxn
];
struct P
{
int x
[4], f
;
friend bool operator < (const P
&a
, const P
&b
) {
for(int i
=3; i
>=0; --i
) {
if(a
.x
[i
]<b
.x
[i
]) return 1;
if(a
.x
[i
]>b
.x
[i
]) return 0;
}
return 0;
}
}p0
[maxn
], p
[maxn
], tmp
[maxn
];
bool cmp(const P
&a
, const P
&b
) {
return a
.x
[Dim
]<b
.x
[Dim
];
}
inline void Max(int &x
, int y
) { if(x
<y
) x
=y
; }
inline void Min(int &x
, int y
) { if(x
>y
) x
=y
; }
inline int new_node() {
if(top
) return rub
[top
--];
return ++tot
;
}
void push_up(int now
) {
for(int i
=0; i
<3; ++i
) {
mi
[now
][i
]=p
[now
].x
[i
];
if(ls
[now
]) Min(mi
[now
][i
],mi
[ls
[now
]][i
]);
if(rs
[now
]) Min(mi
[now
][i
],mi
[rs
[now
]][i
]);
}
mx
[now
]=p
[now
].f
;
if(ls
[now
]) Max(mx
[now
],mx
[ls
[now
]]);
if(rs
[now
]) Max(mx
[now
],mx
[rs
[now
]]);
sz
[now
]=sz
[ls
[now
]]+sz
[rs
[now
]]+1;
}
void to_array(int idx
, int now
) {
if(ls
[now
]) to_array(idx
,ls
[now
]);
tmp
[idx
+sz
[ls
[now
]]]=p
[now
]; rub
[++top
]=now
;
if(rs
[now
]) to_array(idx
+sz
[ls
[now
]]+1,rs
[now
]);
}
void rebuild(int l
, int r
, int dim
, int &now
) {
if(l
>r
) { now
=0; return; }
now
=new_node();
int m
=(l
+r
)/2;
Dim
=dim
; nth_element(tmp
+l
,tmp
+m
,tmp
+r
+1,cmp
); p
[now
]=tmp
[m
];
rebuild(l
,m
-1,(dim
+1)%3,ls
[now
]);
rebuild(m
+1,r
,(dim
+1)%3,rs
[now
]);
push_up(now
);
}
void check(int dim
, int &now
) {
if(sz
[ls
[now
]]*4>sz
[now
]*3||sz
[rs
[now
]]*4>sz
[now
]*3) {
to_array(1,now
); rebuild(1,sz
[now
],dim
,now
);
}
}
void insert(int I
, int dim
, int &now
) {
if(!now
) {
now
=new_node(); p
[now
]=p0
[I
]; ls
[now
]=rs
[now
]=0;
push_up(now
);
return;
}
if(p0
[I
].x
[dim
]<=p
[now
].x
[dim
]) insert(I
,(dim
+1)%3,ls
[now
]);
else insert(I
,(dim
+1)%3,rs
[now
]);
push_up(now
); check(dim
,now
);
}
void query(int I
, int now
) {
if(!now
) return;
int c
=0, &f
=p0
[I
].f
;
for(int i
=0; i
<3; ++i
) if(p
[now
].x
[i
]<=p0
[I
].x
[i
]) c
++;
if(c
==3) Max(f
,p
[now
].f
);
int l
=ls
[now
], r
=rs
[now
];
if(mx
[l
]<mx
[r
]) swap(l
,r
);
int dl
=0, dr
=0;
for(int i
=0; i
<3; ++i
) {
if(mi
[l
][i
]>p0
[I
].x
[i
]) dl
++;
if(mi
[r
][i
]>p0
[I
].x
[i
]) dr
++;
}
if(!dl
&&mx
[l
]>f
) query(I
,l
);
if(!dr
&&mx
[r
]>f
) query(I
,r
);
}
int main() {
n
=read();
for(int i
=1; i
<=n
; ++i
)
scanf("%d%d%d%d", &p0
[i
].x
[0], &p0
[i
].x
[1], &p0
[i
].x
[2], &p0
[i
].x
[3]);
sort(p0
+1,p0
+1+n
);
int ans
=0;
for(int i
=1; i
<=n
; ++i
) {
query(i
,rt
); p0
[i
].f
++;
insert(i
,0,rt
);
Max(ans
,p0
[i
].f
);
}
printf("%d\n", ans
);
}
