这题可以不用二分,有$O(n)$解法
因为这是一个单调序列,我们可以直接用一个数组来存储一种数的区间,最后输出时,直接判断区间是否都为0,不是则输出区间。所以总的复杂度为$O(n+q)$
具体操作请见代码。
`
#include[HTML_REMOVED]
using namespace std;
struct node{int x,y;}b[110500];//用来存储区间的数组
int n,q,x,a[110500];
int num,cas,l,r;//cas来记录上一个数,l记录左区间,r记录右区间
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=cas)
{
r=i-1;
b[cas].y=r;
cas=a[i];
b[a[i]].x=i;
}
if(i==n)b[a[i]].y=i;
}
for(int t=1;t<=q;t++)
{
scanf("%d",&x);
if(b[x].x==0||b[x].y==0)
printf("-1 -1\n");
else printf("%d %d\n",b[x].x-1,b[x].y-1);
}
return 0;
} `
这是一道二分查找的模板题 😭
模拟能过的题干嘛二分,模板题应该是跳石头吧
额…… 二分模板题的作用不就是练习二分吗?