thảo luận Leetcode contest, đường tới Guardian

from copy import copy

class Node:
    def __init__(self, lo=-1, hi=-1):
        self.lo = lo
        self.hi = hi
        self.leftObstacle = None
        self.rightObstacle = None
        self.largestRange = hi - lo


class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.nodes = 4 * n * [None]
        self.buildTree(0, 0, self.n - 1)

    def buildTree(self, root, lo, hi):
        if lo == hi:
            self.nodes[root] = Node(lo, hi)
            return

        mid = (lo + hi) // 2
        self.buildTree(root * 2 + 1, lo, mid)
        self.buildTree(root * 2 + 2, mid + 1, hi)
        self.nodes[root] = self.mergeResult(self.nodes[2 * root + 1], self.nodes[2 * root + 2])

    def mergeResult(self, leftNode, rightNode):
        if not leftNode:
            return copy(rightNode)
        if not rightNode:
            return copy(leftNode)

        node = Node(leftNode.lo, rightNode.hi)
        node.leftObstacle = leftNode.leftObstacle if leftNode.leftObstacle != None else rightNode.leftObstacle
        node.rightObstacle = rightNode.rightObstacle if rightNode.rightObstacle != None else leftNode.rightObstacle

        midLeft = leftNode.rightObstacle if leftNode.rightObstacle != None else leftNode.lo
        midRight = rightNode.leftObstacle if rightNode.leftObstacle != None else rightNode.hi
        node.largestRange = max(leftNode.largestRange, rightNode.largestRange, midRight - midLeft)
        
        return node

    def query(self, qStart, qEnd, root=0, lo=0, hi=-1):
        if hi == -1:
            hi = self.n - 1
        if qStart <= lo <= hi <= qEnd:
            return self.nodes[root]

        if hi < qStart or lo > qEnd:
            return None

        mid = (lo + hi) // 2

        result = self.mergeResult(self.query(qStart, qEnd, 2 * root + 1, lo, mid),
                                  self.query(qStart, qEnd, 2 * root + 2, mid + 1, hi))

        return result

    def update(self, index, root=0, lo=0, hi=-1):
        if hi == -1:
            hi = self.n - 1

        if lo == hi:
            node = self.nodes[root]
            node.leftObstacle = node.rightObstacle = index
            node.largestRange = 0
            return

        mid = (lo + hi) // 2
        if index <= mid:
            self.update(index, 2 * root + 1, lo, mid)
        else:
            self.update(index, 2 * root + 2, mid + 1, hi)

        self.nodes[root] = self.mergeResult(self.nodes[2 * root + 1], self.nodes[2 * root + 2])


class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        ans = []
        segTree = SegmentTree(max(q[1] for q in queries) + 1)
        for q in queries:
            if q[0] == 1:
                segTree.update(q[1])
            else:
                x, sz = q[1], q[2]
                maxSize = segTree.query(0, x).largestRange
                ans.append(maxSize >= sz)

        return ans