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

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

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

ソースコード

#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& key) const {
        u64 x = key.h1 ^ (key.h2 + 0x9e3779b97f4a7c15ULL
                          + (key.h1 << 6) + (key.h1 >> 2));
        x ^= x >> 30;
        x *= 0xbf58476d1ce4e5b9ULL;
        x ^= x >> 27;
        x *= 0x94d049bb133111ebULL;
        x ^= x >> 31;
        return static_cast<size_t>(x);
    }
};

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

struct Query {
    int left;
    int right;
    int id;
};

struct Group {
    int representativeTime = -1;
    vector<Query> queries;
};

class FenwickTree {
private:
    int n;
    vector<int> tree;

public:
    explicit FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    void add(int position, int value) {
        for (int i = position; i <= n; i += i & -i) {
            tree[i] += value;
        }
    }

    int prefixSum(int position) const {
        int result = 0;
        for (int i = position; i > 0; i -= i & -i) {
            result += tree[i];
        }
        return result;
    }

    int rangeSum(int left, int right) const {
        if (left > right) {
            return 0;
        }
        return prefixSum(right) - prefixSum(left - 1);
    }
};

struct RightComparator {
    bool operator()(const Query& a, const Query& b) const {
        if (a.right != b.right) {
            return a.right < b.right;
        }
        return a.left < b.left;
    }
};

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

// 同じ括弧列に属するクエリを、右端を一方向に動かして処理する。
static void solveGroup(
    const string& s,
    vector<Query>& queries,
    vector<int>& answers
) {
    if (queries.empty()) {
        return;
    }

    const int n = static_cast<int>(s.size());

    // 文字列全体を左から貪欲に対応付ける。
    // matchedPairs は閉じ括弧位置の昇順になる。
    vector<int> openStack;
    vector<pair<int, int>> matchedPairs;
    openStack.reserve(n);
    matchedPairs.reserve(n / 2);

    for (int position = 1; position <= n; ++position) {
        if (s[position - 1] == '(') {
            openStack.push_back(position);
        } else if (!openStack.empty()) {
            int openPosition = openStack.back();
            openStack.pop_back();
            matchedPairs.push_back({openPosition, position});
        }
    }

    // クエリの右端を昇順にする。
    sort(queries.begin(), queries.end(), RightComparator{});

    FenwickTree fenwick(n);
    int pairIndex = 0;

    for (const Query& query : queries) {
        // 閉じ括弧位置が query.right 以下のペアを追加する。
        while (
            pairIndex < static_cast<int>(matchedPairs.size()) &&
            matchedPairs[pairIndex].second <= query.right
        ) {
            fenwick.add(matchedPairs[pairIndex].first, 1);
            ++pairIndex;
        }

        // 左括弧位置も [query.left, query.right] にあるペアを数える。
        int pairCount = fenwick.rangeSum(query.left, query.right);
        answers[query.id] = pairCount * 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 (int i = 0; i < Q; ++i) {
        cin >> operations[i].type
            >> operations[i].x
            >> operations[i].y;
    }

    // 各位置に2個の64 bit値を割り当てる。
    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};

    // ')' である位置の値を XOR したものを状態ハッシュとする。
    for (int i = 0; i < N; ++i) {
        if (currentS[i] == ')') {
            currentHash.h1 ^= weight1[i];
            currentHash.h2 ^= weight2[i];
        }
    }

    unordered_map<StateKey, int, StateKeyHash> groupId;
    groupId.reserve(static_cast<size_t>(Q) * 2 + 1);
    groupId.max_load_factor(0.7f);

    vector<Group> groups;
    groups.reserve(Q);

    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;
                currentHash.h1 ^= weight1[position];
                currentHash.h2 ^= weight2[position];
            }
        } else {
            auto it = groupId.find(currentHash);
            int id;

            if (it == groupId.end()) {
                id = static_cast<int>(groups.size());
                groupId.emplace(currentHash, id);
                groups.push_back(Group{});
                groups.back().representativeTime = time;
            } else {
                id = it->second;
            }

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

    // 各グループを、その状態が最初にクエリ2に登場した時刻で処理する。
    vector<vector<int>> groupsAtTime(Q);
    for (int id = 0; id < static_cast<int>(groups.size()); ++id) {
        groupsAtTime[groups[id].representativeTime].push_back(id);
    }

    vector<int> answers(answerCount);
    currentS = initialS;

    // 2回目の走査：代表時刻の文字列を使って各グループを1回だけ解く。
    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 id : groupsAtTime[time]) {
                solveGroup(currentS, groups[id].queries, answers);
            }
        }
    }

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

    return 0;
}