AcWing 789. 数的范围(哈希表)
原题链接
简单
作者:
麦克斯韦妖_7
,
2021-08-21 10:12:05
,
所有人可见
,
阅读 153
/**
* 顺序查找会超时,因此采用哈希表
* 哈希表中存储该数据的起始和结束坐标
* 每次输入时,更新两个坐标
*
**/
#include <iostream>
#include <unordered_map>
using namespace std;
struct Num{
int begin, end;
};
int a[100010];
int main(){
int n, q;
scanf("%d %d", &n, &q);
unordered_map<int, Num> hash;
for(int i = 0; i < n; i ++){
scanf("%d", &a[i]);
if(a[i] != a[i - 1])
hash[a[i]] = {i, i};
else hash[a[i]].end = i;
}
for(int i = 0 ; i < q; i ++){
int cur;
scanf("%d", &cur);
if(!hash.count(cur)) printf("-1 -1\n");
else printf("%d %d\n", hash[cur].begin, hash[cur].end);
}
return 0;
}