四维显然不能跑,我们直接排序一下,然后三维数点,插入到 kdt,dp 一下即可。
// by Isaunoya
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct io {
char buf[1 << 27 | 3], *s;
int f;
io() { f = 0, buf[fread(s = buf, 1, 1 << 27, stdin)] = '\n'; }
io& operator >> (int&x) {
for(x = f = 0; !isdigit(*s); ++s) f |= *s == '-';
while(isdigit(*s)) x = x * 10 + (*s++ ^ 48);
return x = f ? -x : x, *this;
}
};
int f = 0, flag = 0;
const int K = 4;
const int maxn = 1e5 + 51;
struct point {
int d[K], w;
bool operator < (const point& p) const {
if(d[f] ^ p.d[f]) { return d[f] < p.d[f]; }
for(int i = 0 ; i < K - flag ; i ++) {
if(d[i] ^ p.d[i]) { return d[i] < p.d[i]; }
}
return 0;
}
};
void cmax(int&x, const int&y) {
if(x < y) x = y;
}
void cmin(int&x, const int&y) {
if(x > y) x = y;
}
const double alpha = 0.75;
template < short K >
struct KDT {
#define ls son[0]
#define rs son[1]
struct tree {
int sz, mxw;
tree *son[2];
point range, mn, mx;
void up() {
sz = ls -> sz + rs -> sz + 1;
mxw = range.w;
cmax(mxw, ls -> mxw);
cmax(mxw, rs -> mxw);
mx = mn = range;
for(int i = 0 ; i < K ; i ++) {
cmin(mn.d[i], ls -> mn.d[i]);
cmin(mn.d[i], rs -> mn.d[i]);
cmax(mx.d[i], ls -> mx.d[i]);
cmax(mx.d[i], rs -> mx.d[i]);
}
}
bool unb() {
return ls -> sz > sz * alpha || rs -> sz > sz * alpha;
}
bool in(point a, point b) {
for(int i = 0 ; i < K ; i ++)
if(a.d[i] > mn.d[i] || b.d[i] < mx.d[i])
return 0;
return 1;
}
bool out(point a, point b) {
for(int i = 0 ; i < K ; i ++)
if(a.d[i] > mx.d[i] || b.d[i] < mn.d[i])
return 1;
return 0;
}
bool at(point a, point b) {
for(int i = 0 ; i < K ; i ++)
if(range.d[i] < a.d[i] || range.d[i] > b.d[i])
return 0;
return 1;
}
} pool[maxn], * tail, * null, * root, * rec[maxn];
int top;
point down;
void init() {
tail = pool;
null = tail ++;
for(int i = 0 ; i < K ; i ++)
null -> mn.d[i] = 1e18;
for(int i = 0 ; i < K ; i ++)
null -> mx.d[i] = -1e18;
down = null -> mx;
null -> son[0] = null -> son[1] = null;
root = null;
}
tree * newnode(point x) {
tree *p = top ? rec[top --] : tail ++;
p -> son[0] = p -> son[1] = null;
p -> range = p -> mn = p -> mx = x;
p -> mxw = x.w, p -> sz = 1;
return p;
}
point b[maxn];
int cnt;
void trv(tree *p) {
if(p == null) return;
trv(p -> ls);
b[++ cnt] = p -> range;
rec[++ top] = p;
trv(p -> rs);
}
tree * build(int l, int r, int d) {
if(l > r) return null;
int mid = l + r >> 1;
f = d;
nth_element(b + l, b + mid, b + r + 1);
tree * p = newnode(b[mid]);
if(l == r) return p;
p -> ls = build(l, mid - 1, (d + 1) % K);
p -> rs = build(mid + 1, r, (d + 1) % K);
p -> up(); return p;
}
void rebld(tree*&p) {
cnt = 0, trv(p), p = build(1, cnt, 0);
}
int ans;
void qry(tree*p, point a,point b) {
if(p == null) return;
if(p -> out(a, b)) return;
if(p -> in(a, b)) {
cmax(ans, p -> mxw);
return;
}
cmax(ans, p -> at(a, b)? p -> range.w : 0);
if(p -> ls -> mxw > ans) qry(p -> ls, a, b);
if(p -> rs -> mxw > ans) qry(p -> rs, a, b);
}
tree ** ins(tree *&p, point x, int d) {
if(p == null) {
p = newnode(x);
return &null;
}
tree **unb = ins(p -> son[p -> range.d[d] < x.d[d]], x, (d + 1) % K);
p -> up();
if(p -> unb()) unb = &p;
return unb;
}
int qry(point up) {
ans = 0;
qry(root, down, up);
return ans;
}
void ins(point p) {
tree ** unb = ins(root, p, 0);
if(*unb == null) return;
rebld(*unb);
}
};
KDT <K - 1> kdt;
point a[maxn];
signed main() {
#ifdef LOCAL
freopen("testdata.in", "r", stdin);
#endif
kdt.init();
int n;
// io in;
#define in cin
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
in >> n;
for(int i = 1 ; i <= n ; i ++) {
for(int j = 0 ; j < K ; j ++) {
in >> a[i].d[j];
}
}
sort(a + 1, a + n + 1);
flag = 1;
for(int i = 1 ; i <= n ; i ++) {
for(int j = 0 ; j < K - 1 ; j ++)
a[i].d[j] = a[i].d[j + 1];
}
int ans = 0;
for(int i = 1 ; i <= n ; i ++) {
a[i].w = kdt.qry(a[i]) + 1;
ans = max(ans, a[i].w);
kdt.ins(a[i]);
}
cout << ans << '\n';
return 0;
}