作者事先声明：我用的思路可能不太一样

rt，将所有询问离线，使用双指针求解，最后在排序
代码如下

#include <bits/stdc++.h>
using namespace std;
int n,a[1000001],m;
struct num{
	int v,ans,id;
}b[100001]; 
bool cmp1(num x,num y){
	return x.v<y.v;
}
bool cmp2(num x,num y){
	return x.id<y.id;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>b[i].v;
		b[i].id=i;
	}
	sort(b+1,b+m+1,cmp1);
	int i=1,j=1;
	while(i<=n&&j<=m){
		if(a[i]<b[j].v) i++;
		else if(a[i]==b[j].v){
			b[j].ans=i;
			i++,j++;
		}
		else{
			b[j].ans=-1;
			j++;
		}
	}
	for(;j<=m;j++){
		b[j].ans=-1;
	}
	sort(b+1,b+m+1,cmp2);
	for(int i=1;i<=m;i++){
		cout<<b[i].ans<<' ';
	}
	return 0;
}

悬赏一个关注