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

• 問題: No.3652 Range Bracket Sequence
• ユーザー: とある理系大学生の日常
• 提出日時: 2026-08-05 12:23:10
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,898 bytes
• コンパイル時間: 3,886 ms
• コンパイル使用メモリ: 367,124 KB
• 実行使用メモリ: 10,240 KB
• 最終ジャッジ日時: 2026-08-28 21:14:21
• 合計ジャッジ時間: 7,921 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// 隣接要素の差が必ず +1 または -1 である配列に対する O(1) RMQ
class PlusMinusOneRMQ {
private:
    int n = 0;
    int blockSize = 1;
    int blockCount = 0;

    vector<ll> values;
    vector<int> blockMask;
    vector<ll> blockMinimum;

    // ブロック全体に対する Sparse Table
    vector<vector<ll>> sparseTable;
    vector<int> logarithm;

    // patternMinimum[mask][left * blockSize + right]
    vector<vector<int>> patternMinimum;

    void buildPatternTable() {
        int maskCount = 1 << max(0, blockSize - 1);

        patternMinimum.assign(
            maskCount,
            vector<int>(blockSize * blockSize, 0)
        );

        for (int mask = 0; mask < maskCount; ++mask) {
            vector<int> relative(blockSize, 0);

            for (int i = 1; i < blockSize; ++i) {
                bool increases = mask & (1 << (i - 1));
                relative[i] = relative[i - 1] + (increases ? 1 : -1);
            }

            for (int left = 0; left < blockSize; ++left) {
                int currentMinimum = relative[left];

                for (int right = left; right < blockSize; ++right) {
                    currentMinimum = min(currentMinimum, relative[right]);

                    patternMinimum[mask][left * blockSize + right] =
                        currentMinimum;
                }
            }
        }
    }

    ll queryInsideBlock(
        int block,
        int leftOffset,
        int rightOffset
    ) const {
        int blockStart = block * blockSize;
        int mask = blockMask[block];

        return values[blockStart] +
               patternMinimum[mask]
                             [leftOffset * blockSize + rightOffset];
    }

    ll queryWholeBlocks(int leftBlock, int rightBlock) const {
        if (leftBlock > rightBlock) {
            return numeric_limits<ll>::max();
        }

        int length = rightBlock - leftBlock + 1;
        int level = logarithm[length];

        return min(
            sparseTable[level][leftBlock],
            sparseTable[level][rightBlock - (1 << level) + 1]
        );
    }

public:
    void initialize(int maximumSize) {
        int logN = 0;

        while ((1LL << (logN + 1)) <= maximumSize) {
            ++logN;
        }

        blockSize = max(1, logN / 2);
        buildPatternTable();
    }

    void build(const vector<ll>& array) {
        values = array;
        n = static_cast<int>(values.size());

        blockCount = (n + blockSize - 1) / blockSize;

        blockMask.assign(blockCount, 0);
        blockMinimum.assign(
            blockCount,
            numeric_limits<ll>::max()
        );

        for (int block = 0; block < blockCount; ++block) {
            int start = block * blockSize;
            int finish = min(n, start + blockSize);

            int mask = 0;

            for (int i = start + 1; i < finish; ++i) {
                if (values[i] > values[i - 1]) {
                    mask |= 1 << (i - start - 1);
                }
            }

            blockMask[block] = mask;

            for (int i = start; i < finish; ++i) {
                blockMinimum[block] =
                    min(blockMinimum[block], values[i]);
            }
        }

        logarithm.assign(blockCount + 1, 0);

        for (int i = 2; i <= blockCount; ++i) {
            logarithm[i] = logarithm[i / 2] + 1;
        }

        int levelCount = logarithm[blockCount] + 1;

        sparseTable.assign(
            levelCount,
            vector<ll>(blockCount)
        );

        sparseTable[0] = blockMinimum;

        for (int level = 1; level < levelCount; ++level) {
            int length = 1 << level;
            int half = length / 2;

            for (int i = 0; i + length <= blockCount; ++i) {
                sparseTable[level][i] = min(
                    sparseTable[level - 1][i],
                    sparseTable[level - 1][i + half]
                );
            }
        }
    }

    // values[left ... right] の最小値を O(1) で返す
    ll query(int left, int right) const {
        int leftBlock = left / blockSize;
        int rightBlock = right / blockSize;

        int leftOffset = left % blockSize;
        int rightOffset = right % blockSize;

        if (leftBlock == rightBlock) {
            return queryInsideBlock(
                leftBlock,
                leftOffset,
                rightOffset
            );
        }

        ll result = numeric_limits<ll>::max();

        // 左端のブロック
        result = min(
            result,
            queryInsideBlock(
                leftBlock,
                leftOffset,
                blockSize - 1
            )
        );

        // 右端のブロック
        result = min(
            result,
            queryInsideBlock(
                rightBlock,
                0,
                rightOffset
            )
        );

        // 中間にある完全なブロック
        result = min(
            result,
            queryWholeBlocks(
                leftBlock + 1,
                rightBlock - 1
            )
        );

        return result;
    }
};

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

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

    string S;
    cin >> S;

    vector<ll> prefix(N + 1);

    PlusMinusOneRMQ rmq;
    rmq.initialize(N + 1);

    // 累積和と RMQ を O(N) で再構築する
    auto rebuild = [&]() {
        prefix[0] = 0;

        for (int i = 0; i < N; ++i) {
            prefix[i + 1] =
                prefix[i] + (S[i] == '(' ? 1 : -1);
        }

        rmq.build(prefix);
    };

    rebuild();

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

        if (type == 1) {
            int position = x - 1;
            char newCharacter = (y == 1 ? '(' : ')');

            if (S[position] != newCharacter) {
                S[position] = newCharacter;
                rebuild();
            }
        } else {
            int left = x;
            int right = y;

            int length = right - left + 1;

            // 区間 [left, right] の '(' を +1、')' を -1 とした総和
            ll intervalSum =
                prefix[right] - prefix[left - 1];

            // 区間内に存在する ')' の総数
            ll closeCount =
                (length - intervalSum) / 2;

            // prefix[left ... right] の最小値
            ll minimumPrefix =
                rmq.query(left, right);

            // 左側に対応する '(' が存在しない ')' の個数
            ll unmatchedClose = max(
                0LL,
                prefix[left - 1] - minimumPrefix
            );

            ll matchedPairs =
                closeCount - unmatchedClose;

            cout << matchedPairs * 2 << '\n';
        }
    }

    return 0;
}