必须要用二分？[玄关]

Mr_yang1 @ 2024-09-24 20:01:21

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],ds;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1;i<=m;i++){
        scanf("%d",&ds);
        bool f=1;
        for(int j=1;j<=n;j++){
            if(a[j]==ds){printf("%d ",j);f=0;break;}
        }
        if(f)printf("-1 ");
    }
}

by ikunTLE @ 2024-09-24 20:02:59

@Mr_yang1 1，也可以使用 STL

by AKPC @ 2024-09-24 20:03:42

@ikunTLE STL 难道不也是二分？

by jrzhr @ 2024-09-24 20:04:56

@Mr_yang1 你觉得呢，O(nm)可能可以过吗

by Blick_Winkel @ 2024-09-24 20:04:57

对询问离线后双指针

by EmptyAlien @ 2024-09-24 20:05:43

只要是二分题就可以倍增。

by ikunTLE @ 2024-09-24 20:06:18

@ACPC 貌似是的，但是 map

by Blick_Winkel @ 2024-09-24 20:08:35

@EmptyAlien 这题倍增复杂度不如二分啊，n,m 不同阶。

by AKPC @ 2024-09-24 20:08:42

@ikunTLE 哦我以为你说的 lower_bound

by EmptyAlien @ 2024-09-24 20:18:05

@Blick_Winkel ？为啥

by Blick_Winkel @ 2024-09-24 20:21:56

@EmptyAlien 举个例子，n=10^7,m=10^5，倍增的复杂度是 O((n+m)\log n) 而二分的复杂度是 O(n+m\log n)，倍增无法通过而二分可以通过。