AcWing 789. 数的范围 (前缀和)
原题链接
简单
作者:
1pressure
,
2021-02-08 17:37:13
,
所有人可见
,
阅读 239
算法1
(前缀和) $O(N + Q)$
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010, Q = 10010;
const int K = 10010;
int n, k;
int a[N], q[Q];
int s1[K] = {0}, s2[K] = {0};
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
s1[a[i]] ++;
if(i > 1 && a[i] != a[i - 1])
{
s2[a[i]] = i - 1;
}
}
for(int i = 1; i <= k; i++)
{
cin >> q[i];
if(s1[q[i]] > 0)
cout << s2[q[i]] << " " << s2[q[i]] + s1[q[i]] - 1 << endl;
else
cout << "-1 -1" << endl;
}
return 0;
}