thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

class Solution:
    def totalScore(self, hp: int, damage: List[int], requirement: List[int]) -> int:
        limit = [hp-x for x in requirement]
        n = len(limit)
        # for each room, find the first start room that the journey can go over the room
        prefix = [0]*(n+1)
        for i in range(1,n+1):
            prefix[i] = prefix[i-1]+damage[i-1]
        def check(room, k):
            # k <= room
            if k > room:
                return True
            if prefix[room+1]-prefix[k]<= limit[room]:
                return True
            else:
                return False
        ans = 0
        for i in range(n):
            lo,hi = 0, i+1
            while lo<=hi:
                mid = (lo+hi)//2
                if check(i, mid):
                    hi = mid-1
                else:
                    lo = mid+1
            ans += (i-lo+1)
        return ans

class Solution:
    def maxSubgraphScore(self, n: int, edges: List[List[int]], good: List[int]) -> List[int]:
        dp0 = [1 if good[i] else -1 for i in range(len(good))]
        dp1 = [0]*n
        g = defaultdict(list)
        for u,v in edges:
            g[u].append(v)
            g[v].append(u)
        
        def update_down(u,v):
            if dp0[v] > 0:
                dp0[u] += dp0[v]
        def update_up(u,v):
            loss = dp0[v] if dp0[v] > 0 else 0
            gain = 0
            if dp1[u]-loss+gain > 0:
                dp1[v] = dp0[v] + dp1[u]-loss+gain
            else:
                dp1[v] = dp0[v]

        def dfs0(u,p):
            for v in g[u]:
                if v!= p:
                    dfs0(v,u)
                    update_down(u,v)
        
        
        def dfs1(u,p):
            for v in g[u]:
                if v!= p:
                    update_up(u,v)
                    dfs1(v,u)
        
        dfs0(0,0)
        dp1[0] = dp0[0]
        dfs1(0,0)
        return dp1

class SegmentTree:
    """
    Implements a Segment Tree for O(log n) range sum queries and
    O(log n) single-point updates.
    """
    def __init__(self, arr: list[int]):
        """
        Initializes the Segment Tree from an input array.
        Time complexity: O(n) for build.
        """
        self.n = len(arr)
        # The tree array is typically 4 times the size of the input array
        # to guarantee enough space for the full binary tree structure.
        self.tree = [0] * (4 * self.n)
        
        # Store the original array to help calculate update delta
        self.arr = arr
        
        # Build the tree recursively
        if self.n > 0:
            self._build_tree(0, 0, self.n - 1)

    def _build_tree(self, tree_index: int, low: int, high: int) -> None:
        """
        Recursively builds the segment tree.
        tree_index: Index in the self.tree list.
        low, high: The range [low, high] in the original array that
                   this node represents.
        """
        if low == high:
            # Leaf node: store the value of the original array element
            self.tree[tree_index] = self.arr[low]
            return

        mid = low + (high - low) // 2
        
        # Recursively build the left and right children
        left_child_index = 2 * tree_index + 1
        right_child_index = 2 * tree_index + 2
        
        self._build_tree(left_child_index, low, mid)
        self._build_tree(right_child_index, mid + 1, high)
        
        # Internal node: store the sum of its children
        self.tree[tree_index] = self.tree[left_child_index] + self.tree[right_child_index]

    def update(self, i: int, new_val: int) -> None:
        """
        Updates the element at index `i` (0-indexed) to `new_val`.
        Time complexity: O(log n)
        
        Args:
            i (int): The 0-indexed position of the element to update.
            new_val (int): The new value for the element.
        """
        if 0 <= i < self.n:
            self.arr[i] = new_val # Update the original array for reference
            self._update_tree(0, 0, self.n - 1, i, new_val)

    def _update_tree(self, tree_index: int, low: int, high: int, i: int, new_val: int) -> None:
        """
        Recursively updates the tree after a point change.
        """
        if low == high:
            # Reached the leaf node: update its value
            self.tree[tree_index] = new_val
            return

        mid = low + (high - low) // 2
        left_child_index = 2 * tree_index + 1
        right_child_index = 2 * tree_index + 2
        
        if i <= mid:
            # The update is in the left child's range
            self._update_tree(left_child_index, low, mid, i, new_val)
        else:
            # The update is in the right child's range
            self._update_tree(right_child_index, mid + 1, high, i, new_val)

        # After the child is updated, update the current node's sum
        self.tree[tree_index] = self.tree[left_child_index] + self.tree[right_child_index]

    def query_range_sum(self, q_low: int, q_high: int) -> int:
        """
        Calculates the sum of elements in the range [q_low, q_high] (inclusive).
        Time complexity: O(log n)
        
        Args:
            q_low (int): The 0-indexed start of the range (inclusive).
            q_high (int): The 0-indexed end of the range (inclusive).
            
        Returns:
            int: The sum of elements in the specified range.
        """
        if q_low > q_high or q_low < 0 or q_high >= self.n:
            return 0 # Invalid range

        return self._query_tree(0, 0, self.n - 1, q_low, q_high)

    def _query_tree(self, tree_index: int, low: int, high: int, q_low: int, q_high: int) -> int:
        """
        Recursively traverses the tree to find the sum for the query range [q_low, q_high].
        """
        # 1. Complete Overlap: The node's range is fully contained in the query range
        if q_low <= low and high <= q_high:
            return self.tree[tree_index]

        # 2. No Overlap: The node's range is outside the query range
        if high < q_low or low > q_high:
            return 0 # Return identity element for sum (0)

        # 3. Partial Overlap: Split the query and check children
        mid = low + (high - low) // 2
        left_child_index = 2 * tree_index + 1
        right_child_index = 2 * tree_index + 2
        
        left_sum = self._query_tree(left_child_index, low, mid, q_low, q_high)
        right_sum = self._query_tree(right_child_index, mid + 1, high, q_low, q_high)
        
        return left_sum + right_sum
        
class Solution:
    def minDeletions(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        diff = [0]*(n)
        for i in range(1, n):
            if s[i] != s[i - 1]:
                diff[i] = 1
        
        seg = SegmentTree(diff)
        ans = []
        for q in queries:
            if q[0] == 1:
                j = q[1]
                if seg.query_range_sum(j, j) == 1:
                    seg.update(j, 0)
                else:
                    if j > 0:
                        seg.update(j, 1)

                if j + 1 < n:
                    neighbor = seg.query_range_sum(j + 1, j + 1)
                    seg.update(j + 1, 1 - neighbor)
            else:
                l, r = q[1], q[2]
                if l == r:
                    ans.append(0)
                else:
                    length = r - l
                    ans.append(length - seg.query_range_sum(l + 1, r))

        return ans