必须要用二分？[玄关]

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 Blick_Winkel @ 2024-09-24 20:22:21

不过这题 n=10^6 应该还是能过的。

by EmptyAlien @ 2024-09-24 20:31:13

@Blick_Winkel ？

我说的是倍增查找，没说是ST表。

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

@EmptyAlien 倍增查找是什么/yiw

by EmptyAlien @ 2024-09-24 20:38:11

@Blick_Winkel 直接倍增阿。。。

不知道怎么描述/kel/kel/kel

by igAC @ 2024-09-24 20:44:31

@Blick_Winkel 其实就是保证区间长度是 2 的整次幂的二分 /hsh

by igAC @ 2024-09-24 20:45:48

@amend 枚举的是 log2(区间长度) 每次 -1 代表每次长度折半

by wjyppm1403 @ 2024-10-03 08:06:20

可以用蛤吸表逃课 能AC但不建议这么写