1
class RangeFreqQuery {
2
 private:
3
  int size;
4
  unordered_map<int, vector<int>> mp;
5

6
 public:
7
  RangeFreqQuery(vector<int> &arr) {
8
    size = arr.size();
9
    for (int i = 0; i < size; i++) {
10
      mp[arr[i]].push_back(i);
11
    }
12
  }
13
  int query(int left, int right, int value) {
14
    int first = lower_bound(mp[value].begin(), mp[value].end(), left) - mp[value].begin();
15
    int second = upper_bound(mp[value].begin(), mp[value].end(), right) - mp[value].begin();
16
    return second - first;
17
  }
18
};