这道题其实可以不用二分AC!
原理十分简单:由于读入的每一个数均在$1~10000$范围内,完全可以建数组存储每一个值出现的次数与第一次出现的位置
C++代码: (复杂度:$O(n)$)
#include<bits/stdc++.h>
using namespace std;
#define re register
#define Re register
#define MAXN 100005
#define ll long long
int n,q,a[MAXN];
int cnt[10005],st[10005];
inline int read(){//快读,可以忽略
int cnt = 0,s = 1;
char ch;
while(!isdigit(ch = getchar()))if(ch == '-')s = -1;
cnt = ch - '0';
while(isdigit(ch = getchar()))cnt = cnt * 10 + ch - '0';
return s * cnt;
}
int main() {
n = read();q = read();
for(Re int i = 1;i <= n;i++){
a[i] = read();
cnt[a[i]]++;//记录每个值出现的次数
if(st[a[i]] == 0)st[a[i]] = i;//记录每个值第一次出现的位置
}
while(q--){
int tmp,lft = 1,rgt = n,mid;
tmp = read();
if(cnt[tmp] == 0)printf("-1 -1\n");//如果一个数出现的次数为0,说明它不存在
else printf("%d %d\n",st[tmp] - 1,st[tmp] + cnt[tmp] - 2);
}
return 0;
}
大佬这个 inline 函数写的很有意思