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);
}