[ABC248D] Range Count Query 题解

FFTotoro · 2022-11-02 18:16:11 · 题解

本题可以使用二分算法。

具体地，用一个二维数组 v 来存储每个数在数列中的位置。例如，数列为 1,2,3,2,6，那么 v_2=\{2,4\}。

每次询问，就用二分算法找到 v_X 中大于等于 L 的第一个数以及大于 R 的第一个数。将两个数的下标相减，即为区间中包含 X 的个数。二分可以使用 lower_bound 和 upper_bound 实现。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> a(n);
  vector<vector<int> > v(n);
  for(int i=0;i<n;i++)
    cin>>a[i],v[--a[i]].emplace_back(i);
  int q; cin>>q;
  while(q--){
    int l,r,x,c=0; cin>>l>>r>>x,l--,r--,x--;
    int ll=lower_bound(v[x].begin(),v[x].end(),l)-v[x].begin(),
      rr=upper_bound(v[x].begin(),v[x].end(),r)-v[x].begin();
    cout<<rr-ll<<'\n';
  }
  return 0;
}