1
var RangeModule = function () {
2
  this.ranges = [];
3
};
4

5
/**
6
 * @param {number} left
7
 * @param {number} right
8
 * @return {void}
9
 */
10
//Time: O(logN)
11
RangeModule.prototype.addRange = function (left, right) {
12
  const lIdx = this.findIndex(left),
13
    rIdx = this.findIndex(-right);
14
  if (lIdx === this.ranges.length) {
15
    this.ranges.push(left);
16
    this.ranges.push(-right);
17
  } else if (
18
    this.ranges[lIdx] < 0 &&
19
    (this.ranges[rIdx] > 0 || rIdx === this.ranges.length)
20
  ) {
21
    this.ranges.splice(lIdx, rIdx - lIdx, -right);
22
  } else if (this.ranges[lIdx] < 0 && this.ranges[rIdx] < 0) {
23
    this.ranges.splice(lIdx, rIdx - lIdx);
24
  } else if (
25
    this.ranges[lIdx] > 0 &&
26
    (this.ranges[rIdx] > 0 || rIdx === this.ranges.length)
27
  ) {
28
    this.ranges.splice(lIdx, rIdx - lIdx, left, -right);
29
  } else if (this.ranges[lIdx] > 0 && this.ranges[rIdx] < 0) {
30
    this.ranges.splice(lIdx, rIdx - lIdx, left);
31
  }
32
  return null;
33
};
34

35
/**
36
 * @param {number} left
37
 * @param {number} right
38
 * @return {boolean}
39
 */
40
//Time: O(logN)
41
RangeModule.prototype.queryRange = function (left, right) {
42
  const lIdx = this.findIndex(left),
43
    rIdx = this.findIndex(-right);
44
  if (lIdx === this.ranges.length) return false;
45
  if (lIdx + 2 < rIdx) return false;
46
  if (lIdx === rIdx) {
47
    return this.ranges[lIdx] < 0;
48
  } else if (lIdx + 1 === rIdx) {
49
    return this.ranges[lIdx] === left || this.ranges[lIdx] === -right;
50
  }
51
  {
52
    return (
53
      this.ranges[lIdx] === left && Math.abs(this.ranges[lIdx + 1]) === right
54
    );
55
  }
56
};
57

58
/**
59
 * @param {number} left
60
 * @param {number} right
61
 * @return {void}
62
 */
63
//Time: O(logN)
64
RangeModule.prototype.removeRange = function (left, right) {
65
  let lIdx = this.findIndex(left),
66
    rIdx = this.findIndex(-right);
67
  if (lIdx === this.ranges.length) return null;
68
  if (
69
    this.ranges[lIdx] < 0 &&
70
    (this.ranges[rIdx] > 0 || rIdx === this.ranges.length)
71
  ) {
72
    this.ranges.splice(lIdx, rIdx - lIdx, -left);
73
  } else if (this.ranges[lIdx] < 0 && this.ranges[rIdx] < 0) {
74
    this.ranges.splice(lIdx, rIdx - lIdx, -left, right);
75
  } else if (
76
    this.ranges[lIdx] > 0 &&
77
    (this.ranges[rIdx] > 0 || rIdx === this.ranges.length)
78
  ) {
79
    this.ranges.splice(lIdx, rIdx - lIdx);
80
  } else if (this.ranges[lIdx] > 0 && this.ranges[rIdx] < 0) {
81
    this.ranges.splice(lIdx, rIdx - lIdx, right);
82
  }
83
  // console.log(this.ranges)
84
  return null;
85
};
86

87
RangeModule.prototype.findIndex = function (number) {
88
  let l = 0,
89
    r = this.ranges.length;
90
  while (l < r) {
91
    const m = l + ((r - l) >> 1);
92
    if (Math.abs(this.ranges[m]) > Math.abs(number)) {
93
      r = m;
94
    } else if (Math.abs(this.ranges[m]) < Math.abs(number)) {
95
      l = m + 1;
96
    } else {
97
      if (number < 0) {
98
        l = m + 1;
99
      } else {
100
        r = m;
101
      }
102
    }
103
  }
104
  return l;
105
};
106

107
/**
108
 * Your RangeModule object will be instantiated and called as such:
109
 * var obj = new RangeModule()
110
 * obj.addRange(left,right)
111
 * var param_2 = obj.queryRange(left,right)
112
 * obj.removeRange(left,right)
113
 */