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

• 問題: No.3652 Range Bracket Sequence
• ユーザー: あるふぁ
• 提出日時: 2026-09-18 07:33:39
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 342 ms / 2,000 ms
• コード長: 3,427 bytes
• コンパイル時間: 1,296 ms
• コンパイル使用メモリ: 186,872 KB
• 実行使用メモリ: 10,112 KB
• 最終ジャッジ日時: 2026-09-18 07:33:56
• 合計ジャッジ時間: 16,883 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

template<class T> class segtree{
private:
    int n, size;
    vector<T> seg;
    T e;
    function<T(T, T)> op;
public:
    segtree(const vector<T>& A, function<T(T, T)> op, T id) : e(id), op(op){
        n = A.size();
        size = 1;
        while (size < n) size <<= 1;
        seg.assign(2*size, e);
        for (int i = 0; i < n; i++) seg[size+i] = A[i];
        for (int i = size-1; i > 0; i--) seg[i] = op(seg[i<<1], seg[i<<1|1]);
    }

    segtree(int sz, function<T(T, T)> op, T id) : e(id), op(op){
        n = sz;
        size = 1;
        while (size < n) size <<= 1;
        seg.assign(2*size, e);
        for (int i = 0; i < n; i++) seg[size+i] = e;
        for (int i = size-1; i > 0; i--) seg[i] = op(seg[i<<1], seg[i<<1|1]);
    }

    void set(int i, T val){
        i += size;
        seg[i] = val;
        while (i >>= 1) seg[i] = op(seg[i<<1], seg[i<<1|1]);
    }

    T all_prod() const{
        return seg[1];
    }

    T prod(int l, int r) const{
        T L = e, R = e;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1){
            if (l&1) L = op(L, seg[l++]);
            if (r&1) R = op(seg[--r], R);
        }
        return op(L, R);
    }

    T get(int i) const{
        return seg[size+i];
    }

    const T& operator [] (int i) const{
        return seg[size+i];
    }

    void add(int i, T val){
        set(i, get(i)+val);
    }

    template<class F> int max_right(int l, F f) const{
        if (l == n) return n;
        l += size;
        T sm = e;
        do{
            while ((l & 1) == 0) l >>= 1;
            if (!f(op(sm, seg[l]))){
                while (l < size){
                    l <<= 1;
                    if (f(op(sm, seg[l]))){
                        sm = op(sm, seg[l]);
                        l++;
                    }
                }
                return l-size;
            }
            sm = op(sm, seg[l]);
            l++;
        }while((l&-l) != l);
        return n;
    }

    template<class F> int min_left(int r, F f) const{
        if (r == 0) return 0;
        r += size;
        T sm = e;
        do{
            r--;
            while (r > 1 && (r&1)) r >>= 1;
            if (!f(op(seg[r], sm))){
                while (r < size){
                    r = r<<1|1;
                    if (f(op(seg[r], sm))){
                        sm = op(seg[r], sm);
                        r--;
                    }
                }
                return r+1-size;
            }
            sm = op(seg[r], sm);
        }while((r&-r) != r);
        return 0;
    }
};

int main(){
    struct S{
        int l, r, lr;
    };
    auto op = [](S l, S r){
        return S{
            l.l-min(l.l, r.r)+r.l,
            l.r+r.r-min(l.l, r.r),
            l.lr+r.lr+min(l.l, r.r)
        };
    };
    auto e = [](){
        return S{
            0, 0, 0
        };
    };

    int N, Q;
    string T;
    cin >> N >> Q >> T;
    segtree<S> seg(N, op, e());
    for (int i = 0; i < N; i++){
        seg.set(i, S{T[i] == '(', T[i] == ')', 0});
    }

    while (Q--){
        int t;
        cin >> t;
        if (t == 1){
            int i, x;
            cin >> i >> x;
            seg.set(i-1, S{x == 1, x == 2, 0});
        }
        else{
            int l, r;
            cin >> l >> r;
            cout << 2*seg.prod(l-1, r).lr << endl;
        }
    }
}