原题链接 https://www.nowcoder.com/test/8537209/summary
题意 n个数 q个 查询 L,R,K L到R区间内为K的数有多少个 数据范围 n <=300000,q<=300000
解析 对于每次查询必须要 O(logn) 复杂度才行 所以想到二分查找 因为数据是不变的没有增删 所以我们对K进行排序 K值相同的对下标排序
然后 标记一下每个K值的出现范围(新的下标）s[K]到e[K] 然后二分查找 出区间内>=L的最左边位置 和区间内<=R最右边的位置 两个相减就是答案
AC代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=3e6,inf=0x3f3f3f3f; 4 typedef long long ll; 5 struct node 6 { 7 int x,val; 8 }a[maxn]; 9 map<ll,int> s,e; 10 int cmp(node a,node b) 11 { 12 if(a.val==b.val) 13 return a.x<b.x; 14 return a.val<b.val; 15 } 16 int main() 17 { 18 int n,m,t; 19 while(scanf("%d",&n)!=EOF) 20 { 21 for(int i=1;i<=n;i++) 22 { 23 scanf("%d",&a[i].val); 24 a[i].x=i; 25 } 26 sort(a+1,a+n+1,cmp); 27 for(int i=1;i<=n;i++) 28 e[a[i].val]=i; 29 for(int i=n;i>=1;i--) 30 s[a[i].val]=i; 31 scanf("%d",&m); 32 while(m--) 33 { 34 int L,R,K; 35 scanf("%d%d%d",&L,&R,&K); 36 if(s[K]==0) 37 { 38 printf("0\n"); 39 continue; 40 } 41 int l,r; 42 l=s[K],r=e[K]; 43 int ansl=inf; 44 while(l<=r) 45 { 46 int mid=(l+r)/2; 47 if(a[mid].x>=L) 48 { 49 ansl=min(mid,ansl); 50 r=mid-1; 51 } 52 else 53 l=mid+1; 54 } 55 l=s[K],r=e[K]; 56 int ansr=-1; 57 while(l<=r) 58 { 59 int mid=(l+r)/2; 60 if(a[mid].x<=R) 61 { 62 ansr=max(ansr,mid); 63 l=mid+1; 64 } 65 else 66 r=mid-1; 67 } 68 if(ansl==inf||ansr==-1) 69 printf("0\n"); 70 else 71 printf("%d\n",ansr-ansl+1); 72 } 73 } 74 }