efficient binary search
IntuitionThe problem involves managing and querying a dynamic collection of intervals. The key challenge is to ensure efficient updates (merging overlapping int
# Intuition
The problem involves managing and querying a dynamic collection of intervals. The key challenge is to ensure efficient updates (merging overlapping intervals) and accurate counting of distinct integers across all intervals. The merging ensures no duplicate counting, and the count operation avoids recomputation.

# Approach
1. Representation of Intervals:
Maintain a sorted list of intervals where overlapping intervals are merged. Sorting simplifies finding overlap using binary search.
2. Adding Intervals:
- Use bisect_left and bisect_right to locate the potential positions of overlap for the given interval [left, right] within the sorted intervals.
- Adjust left and right to merge overlapping intervals.
- Remove covered intervals and update the merged interval in their place.
- Update the total count by subtracting the number of integers removed and adding the number of integers in the merged interval.
3. Counting:
Simply return the precomputed total count of integers across all intervals.
4. Efficiency:
- Interval addition primarily depends on locating the overlapping range using binary search and merging, which is efficient.
Counting is O(1)
- O(1) since it uses a precomputed variable.

# Complexity
- Time complexity:
add: Binary search O(logn) + merging overlapping intervals O(k), where 
k is the number of overlapping intervals.
count: O(1) since it simply returns a value.

- Space complexity:
O(n), where n is the number of intervals maintained in the sorted list.

# Code
```python3 []
from operator import itemgetter
class CountIntervals:
    def __init__(self):
        self.intervals = []
        self.cnt = 0

    def add(self, left: int, right: int) -> None:
        l = bisect.bisect_left(self.intervals, left, key=itemgetter(0))
        r = bisect.bisect_right(self.intervals, right, key=itemgetter(1))
        if l > 0 and left <= self.intervals[l - 1][1]:
            left = self.intervals[l - 1][0]
            l -= 1

        if r < len(self.intervals) and right >= self.intervals[r][0]:
            right = self.intervals[r][1]
            r += 1

        to_add = right - left + 1
        to_remove = 0
        for i in range(l, r):
            to_remove += self.intervals[i][1] - self.intervals[i][0] + 1

        self.cnt += to_add - to_remove
        self.intervals[l:r] = [[left, right]]

    def count(self) -> int:
        return self.cnt


['Python3']