lc732. 我的日程安排表 iii

题目链接：732. 我的日程安排表 III

题解

LC729. 我的日程安排表 I、LC731. 我的日程安排表 II、LC732. 我的日程安排表 III 三题基本差不多。由于先写的 732，当时写了线段树，所以这三题都用线段树写了。标准区间查询和区间修改题目。

参考代码

class MyCalendarThree:
    def __init__(self):
        self.tree = defaultdict(int)
        self.lazy = defaultdict(int)

    def update(self, start: int, end: int, l: int, r: int, idx: int):
        if r < start or end < l:
            return
        if start <= l and r <= end:
            self.tree[idx] += 1
            self.lazy[idx] += 1
        else:
            mid = (l + r) // 2
            self.update(start, end, l, mid, idx * 2)
            self.update(start, end, mid + 1, r, idx * 2 + 1)
            self.tree[idx] = self.lazy[idx] + max(self.tree[idx * 2], self.tree[idx * 2 + 1])

    def book(self, start: int, end: int) -> int:
        self.update(start, end - 1, 0, 10 ** 9, 1)
        return self.tree[1]