1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

class RangeFreqQuery {
public:
    RangeFreqQuery(std::vector<int>& arr) {
        for (int i = 0; i < arr.size(); ++i) {
            map[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int value) {
        if (left > right) {
            return 0;
        }
        
        auto& v = map[value];
        auto it1 = std::lower_bound(v.begin(), v.end(), left);
        auto it2 = std::lower_bound(v.begin(), v.end(), right + 1);
        return it2 - it1;
    }
    
private:
    std::map<int, std::vector<int>> map;
};

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery* obj = new RangeFreqQuery(arr);
 * int param_1 = obj->query(left,right,value);
 */