分析

可以考虑到 为 结尾的最长的序列。那么 。所以其实这个是个四维偏序。所以我们考虑 来做。时间复杂度为 。但是有几个非常重要的减枝条件。可以参照代码。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
const int N = 5e4 + 1000;
struct Node{int s[4],val;
}A[N];
bool cmp(Node a,Node rhs){
    return a.s[0] < rhs.s[0] || (a.s[0] == rhs.s[0] && (a.s[1] < rhs.s[1] || (a.s[1] == rhs.s[1] && (a.s[2] < rhs.s[2] || (a.s[2] == rhs.s[2] && a.s[3] < rhs.s[3])))));
}
struct Tree{int mx[4],mi[4],ch[2],Max;Node p;}t[N];
int n,size,ans,Ans,rt,tot;
void pushup(int u) {
    int lc = t[u].ch[0],rc = t[u].ch[1];
    t[u].Max = t[u].p.val;
    for(int i = 0;i < 4;i++) {
        t[u].mi[i] = t[u].mx[i] = t[u].p.s[i];
        if(lc) t[u].mx[i] = max(t[u].mx[i],t[lc].mx[i]);
        if(rc) t[u].mx[i] = max(t[u].mx[i],t[rc].mx[i]);
        if(lc) t[u].mi[i] = min(t[u].mi[i],t[lc].mi[i]);
        if(rc) t[u].mi[i] = min(t[u].mi[i],t[rc].mi[i]);
    }
    if(lc) t[u].Max = max(t[u].Max,t[lc].Max);
    if(rc) t[u].Max = max(t[u].Max,t[rc].Max);
}
void ask(int u,Node x) {
    if(!u) return;
    if(t[u].Max <= ans) return;
    for(int i = 0;i < 4;i++) if(t[u].mi[i] > x.s[i]) return;
    if(x.s[0] >= t[u].mx[0] && x.s[1] >= t[u].mx[1] && x.s[2] >= t[u].mx[2] && x.s[3] >= t[u].mx[3]) 
    {ans = max(ans,t[u].Max);};
    if(x.s[0] >= t[u].p.s[0] && x.s[1] >= t[u].p.s[1] && x.s[2] >= t[u].p.s[2] && x.s[3] >= t[u].p.s[3]) 
    {ans = max(ans,t[u].p.val);}
    ask(t[u].ch[0],x);ask(t[u].ch[1],x);
}
void insert(int &u,Node x,int type) {
    if(!u) {
        u = ++size;t[u].p = x;pushup(u);return;
    }
    if(x.s[type] <= t[u].p.s[type]) insert(t[u].ch[0],x,(type+1)%4);
    else insert(t[u].ch[1],x,(type+1)%4);
    pushup(u);
}
int main() {
     // freopen("111.in","r",stdin);
    n = read();
    for(int i = 1;i <= n;i++) {
        for(int j = 0;j < 4;j++) A[i].s[j] = read();

    }
    sort(A + 1,A + 1 + n,cmp);
    for(int i = 1;i <= n;i++) {
        ans = -1;
        ask(rt,A[i]);
        if(ans != -1) A[i].val = ans + 1;
        else A[i].val = 1;
        insert(rt,A[i],0);
        Ans = max(ans + 1,Ans);
    }
    printf("%d\n",Ans);
    return 0;
}