求助（全re）

Diary_51 @ 2024-02-18 18:10:38

#include<bits/stdc++.h>
using namespace std;
long long a[1000005];
int main()
{
    long long n,m,q;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>q;
        if(a[q]==0)
        {
            a[q]=i;
        }
    }
    for(int i=0;i<m;i++)
    {
        cin>>q;
        if(a[q]!=0)
        {
            cout<<a[q]<<" ";
        }
        else
        {
            cout<<-1<<" ";
        }
    }
    return 0;
}

by DFs_YYDS @ 2024-02-18 18:16:06

@Diary_51 a_i 最大 10^9，你用桶，而且只开到 10^6 肯定会爆啊。

by QWQ_123 @ 2024-02-18 18:16:17

@Diary_51 《1 \le q \le 10^9》

by HeYilin @ 2024-02-18 18:18:18

@Diary_51 先不说你拿桶排写二分板子，就 q<=1e9 的数据范围你用1e6+5 的数组当桶肯定RE

by QWQ_123 @ 2024-02-18 18:21:26

建议用map，unordered_map,set,unordered_set

by DFs_YYDS @ 2024-02-18 18:28:42

@QWQ_123 用map有点大材小用个了吧。

by danlao @ 2024-02-18 18:30:44

@QWQ_123 map，unordered_map运用下标来段用元素的操作并不是 O(1),set,unordered_set不支持运用下标来段用元素的操作

by danlao @ 2024-02-18 18:31:20

@yaodiguoan 调用，不是段用

by NEKO_Daze @ 2024-02-18 18:35:13

@QWQ_123 不用这么高级吧……这道题不是标的是二分吗？

而且只需要用 STL 的 lower_bound 不就行了吗？

by QWQ_123 @ 2024-02-18 18:35:22

@yaodiguoan 为什么一定要用下表访问？

而且 map 是 O(\log) 的，我没说是 O(1) 啊。

然后 un_map 可以被卡到 O(n) 也是人尽皆知的事了。

然后 set, un_set 可以通过 lower_bound 来查找罢，而且它也有 find 函数罢

by NEKO_Daze @ 2024-02-18 18:36:25

原做法是桶肯定是会爆的，所以走这个路线应该想不通喵。