2080-range-frequency-queries.js

//////////////////////////////////////////////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)
 */