LC 100314. 物块放置查询

https://leetcode.cn/problems/block-placement-queries/description/

线段树 + 辅助的二叉树。表示上应该要选择有固定值的端点，这里默认就是0. 如果以右边为固定端点的话，更新会特别麻烦。

我看到题解里面还有一个做法是使用逆序来回答所有的提问，这样每个安装障碍物可以变为拆除障碍物。好处是可以使用前缀树，实现起来会更简单一些。

另外这里还需要有个辅助二叉树，它的作用是记录某个点之和之后的障碍物，这样可以更新区间。二叉树最好设置哨兵，这样可以简化许多操作：

前提是要存在这样的数，所以有了哨兵逻辑会简化很多。 

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        maxsz = max([q[1] for q in queries])
        n = maxsz + 2
        t = 0
        while (1 << t) < n:
            t += 1
        n = 1 << t

        INF = 1 << 30
        trees = [0] * (2 * n)

        def update_once(p):
            l, r = 2 * p, 2 * p + 1
            trees[p] = max(trees[l], trees[r])

        def update(p, v):
            p += n
            trees[p] = v
            p = p // 2
            while p:
                update_once(p)
                p = p // 2

        def query(p, s, e, end):
            if e <= end: return trees[p]
            m = (s + e) // 2
            if end <= m:
                return query(2 * p, s, m, end)
            a = trees[2 * p]
            b = query(2 * p + 1, m + 1, e, end)
            return max(a, b)

        ans = []
        from sortedcontainers import SortedList
        sl = SortedList([0, maxsz + 1])
        for q in queries:
            x = q[1]
            idx = sl.bisect_left(x)
            pre = sl[idx - 1]
            if q[0] == 1:
                nxt = sl[idx]
                update(x, x - pre)
                update(nxt, nxt - x)
                sl.add(x)
            else:
                r = query(1, 0, n - 1, pre)
                r = max(r, x - pre)
                # print(r)
                ans.append(r >= q[2])
        return ans