查询数字的最邻近

 

 

 

 这道题目要用二分+桶排的方式解决

函数：

l~r找v

c:靠左/右（‘l’/‘r’）

靠左和靠右用STL函数二分就行，这里讲一下思路，二分出最靠左/右的v值（but二维，在but[v][0~len]区间二分）再判断是否在区间内在区间内输出but[v][a](a为二分的答案)否则输出-1。

最后再考虑一下需要输出-1的特殊情况（区间内没有v、不合法..........）即可

主函数：

调用函数即可

例程：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int > but[N];
int n,m;
int e_f(int l,int r,int v,char c)
{if(l>r||but[v].size()==0||l<=0||r>n) return -1;if(c=='l'){int a=lower_bound(but[v].begin(),but[v].end(),l)-but[v].begin();if(but[v][a]>=l&&but[v][a]<=r) return but[v][a];else return -1;}else if(c=='r'){int a=upper_bound(but[v].begin(),but[v].end(),r)-but[v].begin();a-=1;if(but[v][a]>=l&&but[v][a]<=r) return but[v][a];else return -1;}
}
int main()
{
#ifdef LOCALfreopen( "1.in", "r", stdin );freopen( "1.out", "w", stdout );
#endifscanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int t;scanf("%d",&t);but[t].push_back(i);}while(m--){int l,r,v;scanf("%d%d%d",&l,&r,&v);int a1=e_f(l,r,v,'l');int a2=e_f(l,r,v,'r');int a3=e_f(1,l-1,v,'r');int a4=e_f(r+1,n,v,'l');printf("%d %d %d %d\n",a1,a2,a3,a4);        }return 0;
}