求助满江红

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

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

悬赏一个关注