1
from bisect import bisect_left as bl, bisect_right as br
2

3

4
class RangeModule:
5

6
    def __init__(self):
7
        self._X = []
8

9
    def addRange(self, left: int, right: int) -> None:
10
        # Main Logic
11
        #   If idx(left) or idx(right) is odd, it's in a interval. So don't add it.
12
        #   If idx(left) or idx(right) is even, it's not in any interval. So add it as new interval
13
        #   Slice array[idx(left) : idx(right)]
14
        #       1) both odd: Nothing is added. Merge all middle intervals.
15
        #       2) both even: Add new intervals. Merge all middle intervals
16
        #       3) idx(left) is even: update start point of next interval with left
17
        #       4) idx(right) is even: update end point of previous interval with right
18
        # Bisect_left vs. Bisect_right
19
        #   left need to proceed all interval closing at left, so use Bisect_left
20
        #   right need to go after all interval openning at right, so use Bisect_right
21
        i, j = bl(self._X, left), br(self._X, right)
22
        self._X[i:j] = [left] * (i % 2 == 0) + [right] * (j % 2 == 0)
23

24
    def queryRange(self, left: int, right: int) -> bool:
25
        # Main logic
26
        #   If idx of left/right is odd, it's in a interval. Else it's not.
27
        #   If idx of left&right is the same, they're in the same interval
28
        # Bisect_left vs. Bisect_right
29
        #   [start, end). Start is included. End is not.
30
        #   so use bisect_right for left
31
        #   so use bisect_left for right
32
        i, j = br(self._X, left), bl(self._X, right)
33
        return i == j and i % 2 == 1
34

35
    def removeRange(self, left: int, right: int) -> None:
36
        # Main Logic
37
        #   If idx(left) is odd, the interval that contains left need to change end point to left
38
        #   If idx(right) is odd, the interval that contains right need to change start point to right
39
        #   Else, everything from idx(left) to idx(right) is removed. Nothing is changed.
40
        # Bisect_left vs. Bisect_right
41
        #   Same as addRange
42
        i, j = bl(self._X, left), br(self._X, right)
43
        self._X[i:j] = [left] * (i % 2 == 1) + [right] * (j % 2 == 1)