题意:给一个数组,每次查询输出区间内数字x出现的次数。
每次查询数字x是与其它数字无关的,所以我们可以以每个数字为索引建立一个链表,里面存放它出现的下标,这里可以保证是递增的。每次查询数字x,就在x的链表里面二分即可,即二分找到大于R的第一个数r,大于等于L的第一个数l,ans=r-l。如果是没有出现过的数字可以直接输出0。这里为了方便使用了STL,并加入了最小的下界0和最大的上界(n+1)作为哨兵。
注意这个题时间卡的比较紧,每次遍历1到100000初始化可能会超时,所以取数组中最小和最大的数字区间来初始化。
#include<iostream> #include<vector> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int n,q; vector<]; ]; int main() { while(scanf("%d%d",&n,&q)!=EOF) { ,minn=; ; i<=n; ++i) { scanf("%d",&arr[i]); maxn=max(maxn,arr[i]); minn=min(minn,arr[i]); } for(int i=minn; i<=maxn; ++i) { numb[i].clear(); numb[i].push_back(); } ; i<=n; ++i) numb[arr[i]].push_back(i); for(int i=minn; i<=maxn; ++i) numb[i].push_back(n+); while(q--) { int l,r,h; scanf("%d%d%d",&l,&r,&h); ) puts("); else { int up=upper_bound(numb[h].begin(),numb[h].end(),r)-numb[h].begin(); int down=lower_bound(numb[h].begin(),numb[h].end(),l)-numb[h].begin(); printf("%d\n",up-down); } } } ; }