上下有两个长度为n、位置对应的序列A、B，
其中数的范围均为1~n。若abs(A[i]-B[j]) <= 4，
则A[i]与B[j]间可以连一条边。现要求在边与边不相交的情况下的最大的连边数量。
n <= 10^5。
然后似乎这题给出的是全排列，这样我才会做。。

题解

话说学新姿势了啊。。
这题的话，只要一个数能配对的数比较少的话，我们可以采用一个神奇的方法，把最长公共子序列变成最长上升子序列，然后就可以$nlogn$了
考虑到全排列，所以配对数很少。。
然后呢，对于每一个bi，我们找到他可以配对的ai的位置，从大到小放到数组c里，这里从大到小的意思是防止一个bi配对了两个ai
全部bi都放完后，对c这个新序列跑一次最长上升子序列就是答案了
正确性显然

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1000005;
int n;
int pos[N];
int a[N*10],num=0; 
int f[N];//长度为i的最小值
int get (int x)
{int l=0,r=n;int ans;while (l<=r){int mid=(l+r)>>1;if (f[mid]<x) {ans=mid;l=mid+1;}else r=mid-1;}return ans;
}
int main()
{scanf("%d",&n);for (int u=1;u<=n;u++) {int x;scanf("%d",&x);pos[x]=u;}for (int u=1;u<=n;u++){int x;scanf("%d",&x);int c[10],cnt=0;for (int u=-4;u<=4;u++)if (x+u>=1&&x+u<=n)//合法 c[++cnt]=pos[x+u];sort(c+1,c+1+cnt);for (int u=cnt;u>=1;u--)    a[++num]=c[u];}//for (int u=1;u<=num;u++) printf("%d ",a[u]);memset(f,127,sizeof(f));f[0]=0;//我们现在要求最长上升子序列int ans=0;for (int u=1;u<=num;u++){int i=get(a[u]);f[i+1]=a[u];ans=max(ans,i+1);//printf("%d %d\n",a[u],i);}printf("%d\n",ans);return 0;
}