{"size": 2528, "ext": "js", "max_stars_repo_path": "2080-range-frequency-queries.js", "max_stars_repo_name": "kanhiyaa/leetcode-js", "max_stars_repo_stars_event_min_datetime": "2018-12-21T03:40:55.000Z", "max_stars_repo_stars_event_max_datetime": "2022-03-31T16:04:02.000Z", "max_issues_repo_path": "2080-range-frequency-queries.js", "max_issues_repo_name": "emmanuelkyeremeh/leetcode-js", "max_issues_repo_issues_event_min_datetime": "2019-10-22T17:24:59.000Z", "max_issues_repo_issues_event_max_datetime": "2022-03-31T01:41:12.000Z", "max_forks_repo_path": "2080-range-frequency-queries.js", "max_forks_repo_name": "emmanuelkyeremeh/leetcode-js", "max_forks_repo_forks_event_min_datetime": "2019-05-24T17:13:50.000Z", "max_forks_repo_forks_event_max_datetime": "2022-03-20T23:41:39.000Z"}
{"max_stars_count": 297, "max_issues_count": 3, "max_forks_count": 88, "avg_line_length": 36.1142857143, "max_line_length": 206, "alphanum_fraction": 0.4964398734}
//////////////////////////////////////////////Template/////////////////////////////////////////////////////////////
function Bisect() {
    return { insort_right, insort_left, bisect_left, bisect_right }
    function insort_right(a, x, lo = 0, hi = null) {
        lo = bisect_right(a, x, lo, hi);
        a.splice(lo, 0, x);
    }
    function bisect_right(a, x, lo = 0, hi = null) { // > upper_bound
        if (lo < 0) throw new Error('lo must be non-negative');
        if (hi == null) hi = a.length;
        while (lo < hi) {
            let mid = parseInt((lo + hi) / 2);
            x < a[mid] ? hi = mid : lo = mid + 1;
        }
        return lo;
    }
    function insort_left(a, x, lo = 0, hi = null) {
        lo = bisect_left(a, x, lo, hi);
        a.splice(lo, 0, x);
    }
    function bisect_left(a, x, lo = 0, hi = null) { // >= lower_bound
        if (lo < 0) throw new Error('lo must be non-negative');
        if (hi == null) hi = a.length;
        while (lo < hi) {
            let mid = parseInt((lo + hi) / 2);
            a[mid] < x ? lo = mid + 1 : hi = mid;
        }
        return lo;
    }
}

// counter with {value: array indices (increasing order)}
const counter_value_in_indexA_in = (a_or_s) => { let m = new Map(); let n = a_or_s.length; for (let i = 0; i < n; i++) { if (!m.has(a_or_s[i])) m.set(a_or_s[i], []); m.get(a_or_s[i]).push(i); } return m; };
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

/**
 * @param {number[]} arr
 */
var RangeFreqQuery = function(arr) {
  let a = arr
  this.m = counter_value_in_indexA_in(a)
  this.bi = new Bisect();
};

/** 
 * @param {number} left 
 * @param {number} right 
 * @param {number} value
 * @return {number}
 */
RangeFreqQuery.prototype.query = function(left, right, value) {
    let l = left, r =right, x = value, m = this.m, bi = this.bi
    if (!m.has(x)) return 0;
    let a = m.get(x), len = a.length;
    let min = a[0], max = a[len - 1];
    if (l <= min && r >= max) return len; // cover all
    if (r < min || l > max) return 0; // out of bound
    let lbs = bi.bisect_left(a, l); // needs lbs >= l  (lower bound will find first >= l)
    let ubs = bi.bisect_right(a, r); // needs ubs <= r    (upper bound will find first ubs > r, -1 will guarantee <= r)
    ubs--;
    return ubs - lbs + 1;
};

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

