description
data range
[nle 5 imes 10^4
]
solution
这就是四维偏序了...
好象时间复杂度是(O(n^{frac{5}{3}}))...
因为可以剪枝所以速度快了一些...
code
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FILE "a"
#define Cpy(x,y) (memcpy(x,y,sizeof(x)))
#define Set(x,y) (memset(x,y,sizeof(x)))
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=1e9+7;
const int N=200010;
const int M=205;
const dd pi=acos(-1);
const int inf=2147483647;
const ll INF=1e18+1;
const ll P=100000;
il int read(){
RG int data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=(data<<3)+(data<<1)+(ch^48),ch=getchar();
return data*w;
}
il void file(){
srand(time(NULL)+rand());
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
}
int n,rt,tot,cd,nxt[]={1,2,0};
struct node{int d[4];}p[N];
bool operator <(node x,node y){
if(x.d[0]!=y.d[0])return x.d[0]<y.d[0];
if(x.d[1]!=y.d[1])return x.d[1]<y.d[1];
if(x.d[2]!=y.d[2])return x.d[2]<y.d[2];
if(x.d[3]!=y.d[3])return x.d[3]<y.d[3];
return 0;
}
struct kdnode{int d[3],l[3],r[3],s[2],v,mx;}t[N];
bool operator <(kdnode x,kdnode y){return x.d[cd]<y.d[cd];}
#define ls (t[i].s[0])
#define rs (t[i].s[1])
#define mid ((l+r)>>1)
int l[3],r[3],ans;
il void update(int i){
for(RG int k=0;k<3;k++){
t[i].l[k]=t[i].r[k]=t[i].d[k];
if(ls){
t[i].l[k]=min(t[i].l[k],t[ls].l[k]);
t[i].r[k]=max(t[i].r[k],t[ls].r[k]);
}
if(rs){
t[i].l[k]=min(t[i].l[k],t[rs].l[k]);
t[i].r[k]=max(t[i].r[k],t[rs].r[k]);
}
}
t[i].mx=max(t[i].v,max(t[ls].mx,t[rs].mx));
}
int rebuild(int l,int r,int D){
if(l>r)return 0;
cd=D;nth_element(t+l,t+mid,t+r+1);
t[mid].s[0]=rebuild(l,mid-1,nxt[D]);
t[mid].s[1]=rebuild(mid+1,r,nxt[D]);
update(mid);return mid;
}
void insert(int &i,int D){
if(!i){
i=++tot;Cpy(t[i].d,r);Cpy(t[i].l,r);Cpy(t[i].r,r);
}
if(t[i].d[0]==r[0]&&t[i].d[1]==r[1]&&t[i].d[2]==r[2]){
t[i].v=max(t[i].v,ans);t[i].mx=max(t[i].mx,t[i].v);return;
}
insert(t[i].s[r[D]>t[i].d[D]],nxt[D]);update(i);
}
#define ckm(dd) (l[dd]<=t[i].l[dd]&&t[i].r[dd]<=r[dd])
#define ckd(dd) (l[dd]<=t[i].d[dd]&&t[i].d[dd]<=r[dd])
#define cke(dd) (r[dd]<t[i].l[dd]||t[i].r[dd]<l[dd])
void query(int i,int D){
if(!i||cke(2)||cke(1)||cke(0)||t[i].mx<=ans)return;
if(ckm(2)&&ckm(1)&&ckm(0)){ans=max(ans,t[i].mx);return;}
if(ckd(2)&&ckd(1)&&ckd(0))ans=max(ans,t[i].v);
query(ls,nxt[D]);query(rs,nxt[D]);
}
int main()
{
n=read();
for(RG int i=1;i<=n;i++)for(RG int k=0;k<4;k++)p[i].d[k]=read();
sort(p+1,p+n+1);
for(RG int i=1;i<=n;i++){
for(RG int k=0;k<3;k++)r[k]=p[i].d[k+1];
ans=0;query(rt,0);ans++;
insert(rt,0);
if(i%10000==0)rt=rebuild(1,tot,0);
}
printf("%d
",t[rt].mx);
return 0;
}