結果

問題 No.3652 Range Bracket Sequence
コンテスト
ユーザー 市川瑚麻
提出日時 2026-09-06 19:50:22
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 92 ms / 2,000 ms
+ 337µs
コード長 2,059 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,552 ms
コンパイル使用メモリ 236,104 KB
実行使用メモリ 10,112 KB
最終ジャッジ日時 2026-09-06 19:50:37
合計ジャッジ時間 14,402 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <print>

using namespace std;

struct Node {
    int match;
    int open;
    int close;
};

Node merge(const Node& L, const Node& R) {
    int new_match = min(L.open, R.close);
    return {
        L.match + R.match + new_match,
        L.open + R.open - new_match,
        L.close + R.close - new_match
    };
}

struct SegTree {
    int n;
    vector<Node> tree;

    SegTree(int len, const string& s) {
        n = 1;
        while (n < len) n *= 2;
        tree.assign(2 * n, {0, 0, 0});
        for (int i = 0; i < len; ++i) {
            if (s[i] == '(') tree[n + i] = {0, 1, 0};
            else tree[n + i] = {0, 0, 1};
        }
        for (int i = n - 1; i > 0; --i) {
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
        }
    }

    void update(int idx, char c) {
        idx += n;
        if (c == '(') tree[idx] = {0, 1, 0};
        else tree[idx] = {0, 0, 1};
        while (idx > 1) {
            idx /= 2;
            tree[idx] = merge(tree[2 * idx], tree[2 * idx + 1]);
        }
    }

    Node query(int l, int r, int node, int ql, int qr) {
        if (qr <= l || r <= ql) return {0, 0, 0};
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return merge(query(l, mid, 2 * node, ql, qr), query(mid, r, 2 * node + 1, ql, qr));
    }

    int get_match_chars(int ql, int qr) {
        return query(0, n, 1, ql, qr).match * 2;
    }
};

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

    int n, q;
    if (!(cin >> n >> q)) return 0;

    string s;
    cin >> s;

    SegTree st(n, s);

    for (int i = 0; i < q; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int x, t;
            cin >> x >> t;
            x--;
            st.update(x, (t == 1 ? '(' : ')'));
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            std::println("{}", st.get_match_chars(l, r));
        }
    }

    return 0;
}
0