#1174249 (C++23(gcc16)) No.3652 Range Bracket Sequence

• 問題: No.3652 Range Bracket Sequence
• ユーザー: とある理系大学生の日常
• 提出日時: 2026-07-30 02:17:52
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 152 ms / 2,000 ms
• コード長: 7,755 bytes
• コンパイル時間: 1,969 ms
• コンパイル使用メモリ: 239,804 KB
• 実行使用メモリ: 14,336 KB
• 最終ジャッジ日時: 2026-08-28 21:10:58
• 合計ジャッジ時間: 11,408 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 57

ソースコード

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class LazySegmentTree {
private:
    int size;
    const long long INF = (1LL << 60);

    vector<long long> tree;
    vector<long long> lazy;

    // ノード全体にxを加算
    void apply(int node, long long x) {
        tree[node] += x;
        lazy[node] += x;
    }

    // 遅延値を子へ伝播
    void propagate(int node) {
        if (lazy[node] == 0) {
            return;
        }

        apply(node * 2, lazy[node]);
        apply(node * 2 + 1, lazy[node]);

        lazy[node] = 0;
    }

    /*
    半開区間[queryLeft, queryRight)にxを加算する。

    nodeは半開区間[nodeLeft, nodeRight)を担当する。
    */
    void addSub(
        int queryLeft,
        int queryRight,
        long long x,
        int node,
        int nodeLeft,
        int nodeRight
    ) {
        // 交差していない
        if (nodeRight <= queryLeft || queryRight <= nodeLeft) {
            return;
        }

        // 完全に含まれている
        if (queryLeft <= nodeLeft && nodeRight <= queryRight) {
            apply(node, x);
            return;
        }

        propagate(node);

        int middle = (nodeLeft + nodeRight) / 2;

        addSub(
            queryLeft,
            queryRight,
            x,
            node * 2,
            nodeLeft,
            middle
        );

        addSub(
            queryLeft,
            queryRight,
            x,
            node * 2 + 1,
            middle,
            nodeRight
        );

        tree[node] = min(
            tree[node * 2],
            tree[node * 2 + 1]
        );
    }

    /*
    半開区間[queryLeft, queryRight)の最小値を返す。

    nodeは半開区間[nodeLeft, nodeRight)を担当する。
    */
    long long querySub(
        int queryLeft,
        int queryRight,
        int node,
        int nodeLeft,
        int nodeRight
    ) {
        // 交差していない
        if (nodeRight <= queryLeft || queryRight <= nodeLeft) {
            return INF;
        }

        // 完全に含まれている
        if (queryLeft <= nodeLeft && nodeRight <= queryRight) {
            return tree[node];
        }

        propagate(node);

        int middle = (nodeLeft + nodeRight) / 2;

        long long leftResult = querySub(
            queryLeft,
            queryRight,
            node * 2,
            nodeLeft,
            middle
        );

        long long rightResult = querySub(
            queryLeft,
            queryRight,
            node * 2 + 1,
            middle,
            nodeRight
        );

        return min(leftResult, rightResult);
    }

public:
    explicit LazySegmentTree(const vector<long long>& values) {
        int n = static_cast<int>(values.size());

        size = 1;
        while (size < n) {
            size *= 2;
        }

        tree.assign(size * 2, INF);
        lazy.assign(size * 2, 0);

        // 葉へ初期値を格納
        for (int i = 0; i < n; ++i) {
            tree[size + i] = values[i];
        }

        // 葉から根へ構築
        for (int node = size - 1; node >= 1; --node) {
            tree[node] = min(
                tree[node * 2],
                tree[node * 2 + 1]
            );
        }
    }

    // 閉区間[left, right]にxを加算
    void add(int left, int right, long long x) {
        addSub(
            left,
            right + 1,
            x,
            1,
            0,
            size
        );
    }

    // 閉区間[left, right]の最小値を返す
    long long query(int left, int right) {
        return querySub(
            left,
            right + 1,
            1,
            0,
            size
        );
    }

    // index番目の値を取得
    long long get(int index) {
        int node = 1;
        int nodeLeft = 0;
        int nodeRight = size;

        while (nodeRight - nodeLeft > 1) {
            propagate(node);

            int middle = (nodeLeft + nodeRight) / 2;

            if (index < middle) {
                node = node * 2;
                nodeRight = middle;
            } else {
                node = node * 2 + 1;
                nodeLeft = middle;
            }
        }

        return tree[node];
    }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    string S;
    cin >> S;

    // 各位置の括弧情報
    // 1: '('
    // 2: ')'
    vector<int> state(N);

    // prefix[i] = S[0]～S[i]の累積和
    vector<long long> prefix(N);

    long long balance = 0;

    for (int i = 0; i < N; ++i) {
        if (S[i] == '(') {
            state[i] = 1;
            ++balance;
        } else {
            state[i] = 2;
            --balance;
        }

        prefix[i] = balance;
    }

    LazySegmentTree segmentTree(prefix);

    while (Q--) {
        int type, x, t;
        cin >> type >> x >> t;

        if (type == 1) {
            // 0始まりへ変換
            int index = x - 1;

            if (t == 1) {
                // ')'から'('への変更
                if (state[index] == 2) {
                    /*
                    値が-1から+1へ変わるので、
                    index以降の累積和が2増える。
                    */
                    segmentTree.add(index, N - 1, 2);
                    state[index] = 1;
                }
            } else {
                // '('から')'への変更
                if (state[index] == 1) {
                    /*
                    値が+1から-1へ変わるので、
                    index以降の累積和が2減る。
                    */
                    segmentTree.add(index, N - 1, -2);
                    state[index] = 2;
                }
            }
        } else {
            int left = x - 1;
            int right = t - 1;

            /*
            leftの直前までの累積和。

            left=0の場合、文字列の先頭より前なので0。
            */
            long long base;

            if (left == 0) {
                base = 0;
            } else {
                base = segmentTree.get(left - 1);
            }

            // 元の累積和における[left,right]の最小値
            long long minimum = segmentTree.query(left, right);

            // rightまでの累積和
            long long endBalance = segmentTree.get(right);

            // 部分文字列全体における '(' - ')' の値
            long long total = endBalance - base;

            /*
            部分文字列の途中で累積和が負になった分。

            これは対応する'('が存在しない')'の個数。
            */
            long long unmatchedClose = max(
                0LL,
                base - minimum
            );

            long long length = right - left + 1;

            /*
            最終的に残る文字数は、

            対応しない')'の個数
            +
            対応しない'('の個数

            対応しない'('の個数は
            total + unmatchedClose。

            よって残る文字数は
            total + 2 * unmatchedClose。
            */
            long long answer =
                length
                - total
                - 2 * unmatchedClose;

            cout << answer << '\n';
        }
    }

    return 0;
}