这个做法好像是O(nlog2(n))的,我自己闲的没事搞出来的,大家看看对不对awa。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct Point{
	int val,id;
}a[N];
int n,b[N],m,l[N],cnt,c[N],f[N],g[N],d[N]; 
bool cmp(Point x,Point y){
	if(x.val==y.val)return x.id<y.id;
	return x.val<y.val;
}
int find(int x,int l,int r){
	int ans=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(a[mid].val<x)l=mid+1;
		if(a[mid].val>x)r=mid-1;
		if(a[mid].val==x){
			ans=mid;
			r=mid-1;
		}
	}
	return ans;
}
int main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> a[i].val;
		a[i].id=i;
		c[i]=a[i].val;
	}
	for(int i = 1;i <= m;i++)cin >> b[i];
	sort(c+1,c+1+n);
	sort(a+1,a+1+n,cmp);
	for(int i = 1;i <= n;i++)l[i]=1;
	for(int i = 1;i <= m;i++){
		int x=lower_bound(c+1,c+1+n,b[i])-c;//查找b[i]的是第几个大的数 
		if(c[x]!=b[i]){//如果没找到,就说明a不包括b[i],对答案就没有贡献,杀了它 
			d[i]=-1;
			continue;
		}
		int id=find(b[i],l[x],n);//找到编号最小的那个相同的数 
		d[i]=a[id].id;//映射为原来的编号 
		l[x]=id+1;//为了防止重复,把第x个数的标记更新为目前的答案加1 
	}
	//for(int i = 1;i <= m;i++)cout << d[i] << " ";
	memset(g,0x3f,sizeof(g));
	g[1]=d[1];
	int ans=1;
	for(int i = 2;i <= n;i++){
		if(d[i]>g[ans])g[++ans]=d[i];
		else g[lower_bound(g+1,g+1+ans,d[i])-g]=d[i];
	}
	cout << ans;
	return 0;
}