AcWing 789. 数的范围(非二分版)
原题链接
简单
作者:
O₂
,
2024-04-21 15:37:04
,
所有人可见
,
阅读 1
思路:
预处理出每一个数的左端点和右端点即可
时间复杂度: O($n$+$Q$)
C++ 代码
#include<algorithm>
#include<iostream>
#include<cstring>
#define l first
#define r second
using namespace std;
const int N=100010,M=10010;
typedef pair<int,int>PII;
int n,Q,a[N],cnt[M];
PII num[M];
int main(){
cin>>n>>Q;
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[a[i]]++;
if(a[i]==a[i-1]) num[a[i]].r++;
else{
num[a[i]].l=i;
num[a[i]].r=i;
}
}
while(Q--){
int x;
cin>>x;
if(!cnt[x]) cout<<"-1 -1"<<endl;
else cout<<num[x].l-1<<" "<<num[x].r-1<<endl;
}
return 0;
}