#1174250 (Python3) No.3652 Range Bracket Sequence

• 問題: No.3652 Range Bracket Sequence
• ユーザー: とある理系大学生の日常
• 提出日時: 2026-07-30 02:21:35
• 言語: Python3 (3.14.3 + numpy 2.4.4 + scipy 1.17.1)
• 結果: TLE
• 実行時間: -
• コード長: 5,880 bytes
• コンパイル時間: 324 ms
• コンパイル使用メモリ: 21,540 KB
• 実行使用メモリ: 44,464 KB
• 最終ジャッジ日時: 2026-08-28 21:11:01
• 合計ジャッジ時間: 8,736 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 21 TLE * 1 -- * 35

ソースコード

import sys

input = sys.stdin.readline
INF = 10**18


class LazySegmentTree:
    """
    区間加算・区間最小値取得用の遅延セグメント木。

    range_add(L, R, x):
        半開区間[L, R)にxを加算

    range_min(L, R):
        半開区間[L, R)の最小値を取得

    get(i):
        i番目の値を取得
    """

    __slots__ = ("size", "data", "lazy")

    def __init__(self, values):
        size = 1

        while size < len(values):
            size <<= 1

        self.size = size
        self.data = [INF] * (2 * size)
        self.lazy = [0] * (2 * size)

        # 葉に初期値を格納
        self.data[size:size + len(values)] = values

        # 親を構築
        for node in range(size - 1, 0, -1):
            self.data[node] = min(
                self.data[node << 1],
                self.data[node << 1 | 1]
            )

    def _apply(self, node, x):
        """nodeの区間全体にxを加算する。"""
        self.data[node] += x
        self.lazy[node] += x

    def _push(self, node):
        """nodeの遅延値を子へ伝播する。"""
        x = self.lazy[node]

        if x == 0:
            return

        self._apply(node << 1, x)
        self._apply(node << 1 | 1, x)

        self.lazy[node] = 0

    def range_add(self, left, right, x):
        """半開区間[left, right)にxを加算する。"""
        self._range_add(
            left,
            right,
            x,
            1,
            0,
            self.size
        )

    def _range_add(
        self,
        left,
        right,
        x,
        node,
        node_left,
        node_right
    ):
        # 交差しない
        if node_right <= left or right <= node_left:
            return

        # 完全に含まれる
        if left <= node_left and node_right <= right:
            self._apply(node, x)
            return

        self._push(node)

        middle = (node_left + node_right) >> 1
        left_child = node << 1
        right_child = left_child | 1

        self._range_add(
            left,
            right,
            x,
            left_child,
            node_left,
            middle
        )

        self._range_add(
            left,
            right,
            x,
            right_child,
            middle,
            node_right
        )

        self.data[node] = min(
            self.data[left_child],
            self.data[right_child]
        )

    def range_min(self, left, right):
        """半開区間[left, right)の最小値を返す。"""
        return self._range_min(
            left,
            right,
            1,
            0,
            self.size
        )

    def _range_min(
        self,
        left,
        right,
        node,
        node_left,
        node_right
    ):
        # 交差しない
        if node_right <= left or right <= node_left:
            return INF

        # 完全に含まれる
        if left <= node_left and node_right <= right:
            return self.data[node]

        self._push(node)

        middle = (node_left + node_right) >> 1
        left_child = node << 1
        right_child = left_child | 1

        return min(
            self._range_min(
                left,
                right,
                left_child,
                node_left,
                middle
            ),
            self._range_min(
                left,
                right,
                right_child,
                middle,
                node_right
            )
        )

    def get(self, index):
        """index番目の値を取得する。"""
        node = 1
        node_left = 0
        node_right = self.size

        while node < self.size:
            self._push(node)

            middle = (node_left + node_right) >> 1

            if index < middle:
                node <<= 1
                node_right = middle
            else:
                node = node << 1 | 1
                node_left = middle

        return self.data[node]


N, Q = map(int, input().split())
S = list(input().strip())

# prefix# S[0]からS[i]までで、'('を+1、')'を-1とした累積和
prefix = []
balance = 0

for char in S:
    if char == "(":
        balance += 1
    else:
        balance -= 1

    prefix.append(balance)

segment_tree = LazySegmentTree(prefix)

answers = []

for _ in range(Q):
    query_type, x, t = map(int, input().split())

    if query_type == 1:
        index = x - 1
        new_char = "(" if t == 1 else ")"

        # 同じ文字への変更なら何もしない
        if S[index] == new_char:
            continue

        if new_char == "(":
            # ')'から'('なので-1から+1へ変化
            delta = 2
        else:
            # '('から')'なので+1から-1へ変化
            delta = -2

        # index以降の累積和がすべて変化する
        segment_tree.range_add(index, N, delta)
        S[index] = new_char

    else:
        # 0始まりの半開区間[left, right)に変換
        left = x - 1
        right = t

        # leftの直前までの累積和
        if left == 0:
            base = 0
        else:
            base = segment_tree.get(left - 1)

        # 元の累積和における[left, right)の最小値
        minimum = segment_tree.range_min(left, right)

        # right-1までの累積和
        end_balance = segment_tree.get(right - 1)

        # 部分文字列全体での '(' の個数 - ')' の個数
        total_balance = end_balance - base

        # 対応する'('が存在しない')'の個数
        unmatched_close = max(0, base - minimum)

        length = right - left

        # 削除できる最大文字数
        answer = (
            length
            - total_balance
            - 2 * unmatched_close
        )

        answers.append(str(answer))

print("\n".join(answers))