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

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

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

ソースコード

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

using u64 = uint64_t;

struct StateKey {
    u64 h1;
    u64 h2;

    bool operator==(const StateKey& other) const {
        return h1 == other.h1 && h2 == other.h2;
    }
};

struct StateKeyHash {
    size_t operator()(const StateKey& x) const {
        u64 z = x.h1 ^
                (x.h2 +
                 0x9e3779b97f4a7c15ULL +
                 (x.h1 << 6) +
                 (x.h1 >> 2));

        z ^= z >> 30;
        z *= 0xbf58476d1ce4e5b9ULL;
        z ^= z >> 27;
        z *= 0x94d049bb133111ebULL;
        z ^= z >> 31;

        return static_cast<size_t>(z);
    }
};

struct Operation {
    int type;
    int x;
    int y;
};

struct Query {
    int l;
    int r;
    int id;
};

struct Group {
    // この括弧列が最初にクエリ2で登場した時刻
    int representativeTime = -1;

    // この括弧列に対するクエリ2
    vector<Query> queries;
};

struct MoComparator {
    int blockSize;

    bool operator()(const Query& a, const Query& b) const {
        int blockA = a.l / blockSize;
        int blockB = b.l / blockSize;

        if (blockA != blockB) {
            return blockA < blockB;
        }

        if (blockA & 1) {
            return a.r > b.r;
        }

        return a.r < b.r;
    }
};

static u64 splitmix64(u64 x) {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) *
        0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) *
        0x94d049bb133111ebULL;

    return x ^ (x >> 31);
}

// 同じ括弧列に対するクエリ2をMo's Algorithmで処理
static void solveGroup(
    const string& S,
    vector<Query>& queries,
    vector<int>& answers
) {
    if (queries.empty()) {
        return;
    }

    int N = static_cast<int>(S.size());

    /*
        '(' を +1
        ')' を -1
        とした累積和
    */
    vector<int> prefix(N + 1, 0);

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

    int blockSize = max(
        1,
        static_cast<int>(
            N / sqrt(static_cast<double>(queries.size()))
        )
    );

    sort(
        queries.begin(),
        queries.end(),
        MoComparator{blockSize}
    );

    /*
        現在のMo区間 [currentLeft, currentRight] に、
        prefix[currentLeft ... currentRight] を保持する。

        クエリ [l, r] で必要なのは、
        prefix[l ... r] の最小値。
    */
    multiset<int> values;

    int currentLeft = 0;
    int currentRight = -1;

    for (const Query& query : queries) {
        while (currentLeft > query.l) {
            --currentLeft;
            values.insert(prefix[currentLeft]);
        }

        while (currentRight < query.r) {
            ++currentRight;
            values.insert(prefix[currentRight]);
        }

        while (currentLeft < query.l) {
            auto it = values.find(prefix[currentLeft]);
            values.erase(it);
            ++currentLeft;
        }

        while (currentRight > query.r) {
            auto it = values.find(prefix[currentRight]);
            values.erase(it);
            --currentRight;
        }

        int length =
            query.r - query.l + 1;

        int intervalSum =
            prefix[query.r] -
            prefix[query.l - 1];

        // 区間内の ')' の総数
        int closeCount =
            (length - intervalSum) / 2;

        int minimumPrefix =
            *values.begin();

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

        int matchedPairs =
            closeCount - unmatchedClose;

        answers[query.id] =
            matchedPairs * 2;
    }
}

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

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

    string initialS;
    cin >> initialS;

    vector<Operation> operations(Q);

    for (Operation& operation : operations) {
        cin >> operation.type
            >> operation.x
            >> operation.y;
    }

    /*
        各位置に2種類の64bit乱数を割り当てる。

        位置iが ')' なら、その位置の乱数を
        全体ハッシュにXORする。
    */
    vector<u64> weight1(N);
    vector<u64> weight2(N);

    for (int i = 0; i < N; ++i) {
        weight1[i] = splitmix64(
            0x123456789abcdef0ULL +
            static_cast<u64>(i)
        );

        weight2[i] = splitmix64(
            0xfedcba9876543210ULL +
            static_cast<u64>(i)
        );
    }

    string currentS = initialS;

    StateKey currentHash{0, 0};

    for (int i = 0; i < N; ++i) {
        if (currentS[i] == ')') {
            currentHash.h1 ^= weight1[i];
            currentHash.h2 ^= weight2[i];
        }
    }

    /*
        括弧列のハッシュからグループ番号への対応。
    */
    unordered_map<
        StateKey,
        int,
        StateKeyHash
    > groupId;

    vector<Group> groups;

    int answerCount = 0;

    /*
        第1走査。

        同一の括弧列に対するクエリ2を
        同じグループへまとめる。
    */
    for (int time = 0; time < Q; ++time) {
        const Operation& operation =
            operations[time];

        if (operation.type == 1) {
            int position =
                operation.x - 1;

            char nextCharacter =
                (operation.y == 1 ? '(' : ')');

            if (currentS[position] != nextCharacter) {
                currentS[position] =
                    nextCharacter;

                /*
                    その位置の状態だけが反転したので、
                    XORでハッシュをO(1)更新。
                */
                currentHash.h1 ^=
                    weight1[position];

                currentHash.h2 ^=
                    weight2[position];
            }
        } else {
            auto it =
                groupId.find(currentHash);

            int group;

            if (it == groupId.end()) {
                group =
                    static_cast<int>(groups.size());

                groupId.emplace(
                    currentHash,
                    group
                );

                groups.push_back(Group{});

                groups.back().representativeTime =
                    time;
            } else {
                group = it->second;
            }

            groups[group].queries.push_back({
                operation.x,
                operation.y,
                answerCount
            });

            ++answerCount;
        }
    }

    /*
        どの時刻で、どの括弧列グループを
        処理するかを記録する。
    */
    vector<vector<int>> groupsAtTime(Q);

    for (
        int group = 0;
        group < static_cast<int>(groups.size());
        ++group
    ) {
        int time =
            groups[group].representativeTime;

        groupsAtTime[time].push_back(group);
    }

    vector<int> answers(answerCount);

    /*
        第2走査。

        各異なる括弧列について、
        最初に登場した時刻で一度だけ
        Mo's Algorithmを実行する。
    */
    currentS = initialS;

    for (int time = 0; time < Q; ++time) {
        const Operation& operation =
            operations[time];

        if (operation.type == 1) {
            currentS[operation.x - 1] =
                (operation.y == 1 ? '(' : ')');
        } else {
            for (int group : groupsAtTime[time]) {
                solveGroup(
                    currentS,
                    groups[group].queries,
                    answers
                );
            }
        }
    }

    for (int answer : answers) {
        cout << answer << '\n';
    }

    return 0;
}