思路

无论如何，总得先把可以连的边先建出来吧？

设 $dp_{i}$ 表示考虑到第 $i$ 条可以连接的边，且这条边必须连，可以连边的最大值。

显然有 $dp_i=\max(dp_j|x_j<x_i,y_j<y_i)+1$。

显然，区间最大值可以用线段树维护。

因为总共只有 $9n$ 条可以连的边，故时间复杂度为 $O(n \log n)$。

code

#include<bits/stdc++.h>
using namespace std;
int n;
int const maxn=500000;
int a[maxn+1];
int b[maxn+1];
struct To{
	int from,to;
}to[maxn*11+1];
int cnt;
int ca[maxn+1];
int f[maxn+1];
int tree[maxn*6+1];
void change(int p,int l,int r,int x,int c){
	if(l==r){
		tree[p]=max(tree[p],c);
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid){
		change(p*2,l,mid,x,c);
	}
	else{
		change(p*2+1,mid+1,r,x,c);
	}
	tree[p]=max(tree[p*2],tree[p*2+1]);
	return;
}
int find(int p,int l,int r,int L,int R){
	if(L>R){
		return 0;
	}
	if(l>=L&&r<=R){
		return tree[p];
	}
	int mid=(l+r)>>1;
	int sum=0;
	if(L<=mid){
		sum=max(sum,find(p*2,l,mid,L,R));
	}
	if(R>mid){
		sum=max(sum,find(p*2+1,mid+1,r,L,R));
	}
	return sum;
}
int ans=0;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		ca[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
		for(int j=max(1,b[i]-4);j<=min(n,b[i]+4);j++){
			if(ca[j]!=0){
				cnt++;
				to[cnt].from=i;
				to[cnt].to=ca[j];
			}
		}
	}
	sort(to+1,to+cnt+1,[](To a,To b){return a.from==b.from?a.to<b.to:a.from<b.from;});
	int j=1;
	for(int i=1;i<=cnt;){
		while(to[i].from==to[j].from){
			f[j]=find(1,1,n,1,to[j].to-1)+1;
			ans=max(ans,f[j]);
			j++;
		}
		while(i<j){
			change(1,1,n,to[i].to,f[i]);
			i++;
		}
//		printf("%d===%d===\n",i,j);
	}
	printf("%d",ans);
	
	return 0;
}