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

• 問題: No.3652 Range Bracket Sequence
• ユーザー: yuki4869.
• 提出日時: 2026-08-29 00:49:20
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 90 ms / 2,000 ms
• コード長: 15,128 bytes
• コンパイル時間: 4,556 ms
• コンパイル使用メモリ: 392,028 KB
• 実行使用メモリ: 15,104 KB
• 最終ジャッジ日時: 2026-08-29 00:49:34
• 合計ジャッジ時間: 12,391 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std; using namespace atcoder;
using ll=long long; using LL=__int128; using mint=modint998244353;
using pll=pair<ll,ll>; using tu=tuple<ll,ll,ll>; using vl=vector<ll>; using vb=vector<bool>; using vvb=vector<vb>; using vvl=vector<vl>; using vs=vector<string>; using vld=vector<long double>; using vc=vector<char>; using vmi=vector<mint>;
using Graph=vector<vector<pair<ll,ll>>>; using graph=vector<vector<ll>>;
template<class T> using rpq=priority_queue<T,vector<T>,greater<T>>; // 小さい順priority_queue
using inverse_priority_queue=rpq<ll>;
const ll Inf=2147483647LL, Inf9=1000000000LL, inf=9223372036854775807LL, inf18=1000000000000000000LL, mod=998244353LL;
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rep3(i,s,t) for(ll i=(ll)(s);i<(ll)(t);i++)
#define pb push_back
#define p(s) cout<<(s)<<'\n'
#define p2(s,t) cout<<(s)<<" "<<(t)<<'\n'
#define p3(s,t,u) cout<<(s)<<" "<<(t)<<" "<<(u)<<'\n'
#define p4(s,t,u,v) cout<<(s)<<" "<<(t)<<" "<<(u)<<" "<<(v)<<'\n'
#define pe(s) cout<<(s)<<' '
#define pval(s) cout<<(s).val()<<'\n'
#define Sort(A) sort(all(A))
#define RSort(A) sort(rall(A))
#define p_yes() p("Yes")
#define p_no() p("No")

template<class T> inline ll sz(const T& x){return (ll)x.size();} // サイズ取得
ostream& operator<<(ostream& os,const mint& x){return os<<x.val();} // mint出力
istream& operator>>(istream& is,mint& x){ll v; is>>v; x=mint(v); return is;} // mint入力
template<class T> inline bool chmin(T& a,const T& b){if(a>b){a=b; return true;} return false;} // 最小値更新
template<class T> inline bool chmax(T& a,const T& b){if(a<b){a=b; return true;} return false;} // 最大値更新
template<class T,class U> ll LB(const vector<T>& v,const U& a){return lower_bound(all(v),a)-v.begin();} // lower_boundのindex
template<class T,class U> ll UB(const vector<T>& v,const U& a){return upper_bound(all(v),a)-v.begin();} // upper_boundのindex
template<class T> T vec_min(const vector<T>& v){assert(!v.empty()); return *min_element(all(v));} // vectorの最小値
template<class T> T vec_max(const vector<T>& v){assert(!v.empty()); return *max_element(all(v));} // vectorの最大値
template<class T> T vec_sum(const vector<T>& v){T res=T(0); for(const auto& x:v) res+=x; return res;} // vectorの総和

template<class T=ll> vector<T> cin_vl(ll n){vector<T> ret(n); rep(i,n) cin>>ret[i]; return ret;} // vector入力、型省略時ll
template<class T=ll> vector<vector<T>> cin_vvl(ll h,ll w){vector<vector<T>> ret(h,vector<T>(w)); rep(i,h) rep(j,w) cin>>ret[i][j]; return ret;} // h*w入力、型省略時ll
template<class T=ll> pair<vector<T>,vector<T>> cin_xy(ll n){vector<T> x(n),y(n); rep(i,n) cin>>x[i]>>y[i]; return {x,y};} // x,y入力、型省略時ll
template<class T=ll> tuple<vector<T>,vector<T>,vector<T>> cin_xyz(ll n){vector<T> x(n),y(n),z(n); rep(i,n) cin>>x[i]>>y[i]>>z[i]; return {x,y,z};} // x,y,z入力、型省略時ll
template<class T=ll> vector<vector<T>> Cin_vl(ll n,ll k){vector<vector<T>> ret(k,vector<T>(n)); rep(i,n) rep(j,k) cin>>ret[j][i]; return ret;} // n行k列入力を列ごと保持、型省略時ll
template<class T=ll> vector<pair<T,T>> cin_pairs(ll n){vector<pair<T,T>> ret(n); rep(i,n) cin>>ret[i].first>>ret[i].second; return ret;} // pair列入力、型省略時ll
template<class T=ll> vector<tuple<T,T,T>> cin_tuples(ll n){vector<tuple<T,T,T>> ret(n); rep(i,n){T a,b,c; cin>>a>>b>>c; ret[i]={a,b,c};} return ret;} // 3要素tuple列入力、型省略時ll

template<class T> void cout_vl(const vector<T>& a,char sep=' ',char end='\n'){rep(i,sz(a)){if(i) cout<<sep; cout<<a[i];} cout<<end;} // vector出力
template<class T> void Cout_vl(const vector<T>& a,const vector<T>& b){rep(i,sz(a)) cout<<a[i]<<" "<<b[i]<<'\n';} // 2vector縦出力
template<class T> void cout_vvl(const vector<vector<T>>& a){for(const auto& e:a) cout_vl(e);} // 2次元vector出力

ll ceil_div(ll a,ll b){assert(b!=0); if(b<0) a=-a,b=-b; if(a>=0) return (a+b-1)/b; return -((-a)/b);} // 切り上げ除算
ll floor_div(ll a,ll b){assert(b!=0); if(b<0) a=-a,b=-b; if(a>=0) return a/b; return -((-a+b-1)/b);} // 切り下げ除算
ll isqrt(ll n){ll x=sqrtl(n); while((LL)(x+1)*(x+1)<=n) x++; while((LL)x*x>n) x--; return x;} // floor(sqrt(n))
template<class T> vector<T> sort_unique_vec(vector<T> v){sort(all(v)); v.erase(unique(all(v)),v.end()); return v;} // sortして重複削除した新vector
template<class T> vector<ll> compress(const vector<T>& v){auto xs=sort_unique_vec(v); vector<ll> ret; for(auto& x:v) ret.pb(LB(xs,x)); return ret;} // 座標圧縮後のindex列
template<class T> vector<T> prefix_sum(const vector<T>& v){vector<T> s(sz(v)+1,0); rep(i,sz(v)) s[i+1]=s[i]+v[i]; return s;} // 1次元累積和
template<class T> T range_sum(const vector<T>& s,ll l,ll r){return s[r]-s[l];} // 累積和から[l,r)の和
template<class T> vector<pair<T,ll>> run_length(const vector<T>& v){vector<pair<T,ll>> ret; for(auto& x:v){if(ret.empty()||ret.back().first!=x) ret.pb({x,1}); else ret.back().second++;} return ret;} // ランレングス圧縮
vector<pair<char,ll>> run_length(const string& s){vector<pair<char,ll>> ret; for(char c:s){if(ret.empty()||ret.back().first!=c) ret.pb({c,1}); else ret.back().second++;} return ret;} // 文字列ランレングス圧縮
template<class T> ll argmin(const vector<T>& v){assert(!v.empty()); return min_element(all(v))-v.begin();} // 最小値のindex
template<class T> ll argmax(const vector<T>& v){assert(!v.empty()); return max_element(all(v))-v.begin();} // 最大値のindex
template<class T> bool in_vec(const vector<T>& v,const T& x){return binary_search(all(v),x);} // sort済vectorに存在するか

ll gcd(ll a,ll b){if(b==0) return abs(a); return gcd(b,a%b);} // 最大公約数
ll lcm(ll a,ll b){return a/gcd(a,b)*b;} // 最小公倍数
ll Exp(ll x,ll y){ll cnt=-1; while(x>0) x/=y,cnt++; return cnt;} // y進桁数-1
ll powmod(ll x,ll k,ll m){if(k==0) return 1%m; ll r=powmod(x,k/2,m); r=(LL)r*r%m; if(k&1) r=(LL)r*x%m; return r;} // mod累乗
template<class T> T square(T x){return x*x;} // 二乗
template<class T> void Uni_erase(vector<T>& v){sort(all(v)); v.erase(unique(all(v)),v.end());} // sortして重複削除
inline bool OutIn(ll x,ll y,ll h,ll w){return 0<=x&&x<h&&0<=y&&y<w;} // グリッド範囲内判定
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll Random(ll l,ll r){uniform_int_distribution<ll> dist(l,r-1); return dist(rng);} // [l,r)乱数
void YesNo(bool x){x?p_yes():p_no();} // Yes/No出力
vl vl_n(ll n){vl ret(n); rep(i,n) ret[i]=i; return ret;} // 0..n-1のvector生成

vl dx={0,1,0,-1}, dy={1,0,-1,0};
vl dx8={1,1,0,-1,-1,-1,0,1}, dy8={0,1,1,1,0,-1,-1,-1}; // 8近傍

vector<mint> fac,finv;
void factorial(ll N=1000000LL){ll M=N+100; fac.assign(M+1,1); finv.assign(M+1,1); rep1(i,M) fac[i]=fac[i-1]*i; finv[M]=fac[M].inv(); for(ll i=M;i>=1;i--) finv[i-1]=finv[i]*i;} // N+100まで階乗・逆階乗前計算
void ensure_factorial(ll N){if((ll)fac.size()>N) return; factorial(N);} // 階乗表の不足分確保
mint nCr(ll N,ll r){if(N<0||r<0||N<r) return 0; ensure_factorial(N); return fac[N]*finv[r]*finv[N-r];} // 二項係数
mint nPr(ll N,ll r){if(N<0||r<0||N<r) return 0; ensure_factorial(N); return fac[N]*finv[N-r];} // 順列数

//SegTree

template<class S,S(*op)(S,S),S(*e)()>
struct SegBase:segtree<S,op,e>{
    using Base=segtree<S,op,e>;
    using Base::Base;
};

namespace SegMax_impl{ll op(ll a,ll b){return max(a,b);}ll e(){return -inf;}}
namespace SegMin_impl{ll op(ll a,ll b){return min(a,b);}ll e(){return inf;}}
namespace SegSum_impl{ll op(ll a,ll b){return a+b;}ll e(){return 0;}}
namespace SegXOR_impl{ll op(ll a,ll b){return a^b;}ll e(){return 0;}}
namespace SegOR_impl{ll op(ll a,ll b){return a|b;}ll e(){return 0;}}
namespace SegAND_impl{ll op(ll a,ll b){return a&b;}ll e(){return ~0LL;}}
namespace SegGCD_impl{ll op(ll a,ll b){return gcd(a,b);}ll e(){return 0;}}

using SegMax=SegBase<ll,SegMax_impl::op,SegMax_impl::e>;
using SegMin=SegBase<ll,SegMin_impl::op,SegMin_impl::e>;
using SegSum=SegBase<ll,SegSum_impl::op,SegSum_impl::e>;
using SegXOR=SegBase<ll,SegXOR_impl::op,SegXOR_impl::e>;
using SegOR=SegBase<ll,SegOR_impl::op,SegOR_impl::e>;
using SegAND=SegBase<ll,SegAND_impl::op,SegAND_impl::e>;
using SegGCD=SegBase<ll,SegGCD_impl::op,SegGCD_impl::e>;

namespace SegMinMax_impl{
    struct S{ll mx,mn;};
    S op(S a,S b){return {max(a.mx,b.mx),min(a.mn,b.mn)};}
    S e(){return {-inf,inf};}
}
struct SegMinMax:SegBase<SegMinMax_impl::S,SegMinMax_impl::op,SegMinMax_impl::e>{
    using S=SegMinMax_impl::S;
    using Base=SegBase<S,SegMinMax_impl::op,SegMinMax_impl::e>;
    using Base::Base; using Base::set;
    static vector<S> cv(const vector<ll>&a){vector<S>v;v.reserve(a.size());for(ll x:a)v.pb({x,x});return v;}
    SegMinMax(const vector<ll>&a):Base(cv(a)){}
    void set(int i,ll x){Base::set(i,{x,x});}
};

namespace SegArgMax_impl{
    struct S{ll val,id;};
    S op(S a,S b){return a.val!=b.val?(a.val>b.val?a:b):(a.id<b.id?a:b);}
    S e(){return {-inf,inf};}
}
struct SegArgMax:SegBase<SegArgMax_impl::S,SegArgMax_impl::op,SegArgMax_impl::e>{
    using S=SegArgMax_impl::S;
    using Base=SegBase<S,SegArgMax_impl::op,SegArgMax_impl::e>;
    using Base::Base; using Base::set;
    static vector<S> cv(const vector<ll>&a){vector<S>v;rep(i,sz(a))v.pb({a[i],i});return v;}
    SegArgMax(const vector<ll>&a):Base(cv(a)){}
    void set(int i,ll x){Base::set(i,{x,i});}
};

namespace SegArgMin_impl{
    struct S{ll val,id;};
    S op(S a,S b){return a.val!=b.val?(a.val<b.val?a:b):(a.id<b.id?a:b);}
    S e(){return {inf,inf};}
}
struct SegArgMin:SegBase<SegArgMin_impl::S,SegArgMin_impl::op,SegArgMin_impl::e>{
    using S=SegArgMin_impl::S;
    using Base=SegBase<S,SegArgMin_impl::op,SegArgMin_impl::e>;
    using Base::Base; using Base::set;
    static vector<S> cv(const vector<ll>&a){vector<S>v;rep(i,sz(a))v.pb({a[i],i});return v;}
    SegArgMin(const vector<ll>&a):Base(cv(a)){}
    void set(int i,ll x){Base::set(i,{x,i});}
};

namespace SegMaxSubarray_impl{
    const ll NEG=-(1LL<<60);
    struct S{ll sum,pref,suff,best;};
    S gen(ll x){return {x,x,x,x};}
    S op(S a,S b){
        return {a.sum+b.sum,max(a.pref,a.sum+b.pref),max(b.suff,b.sum+a.suff),max({a.best,b.best,a.suff+b.pref})};
    }
    S e(){return {0,NEG,NEG,NEG};}
}
struct SegMaxSubarray:SegBase<SegMaxSubarray_impl::S,SegMaxSubarray_impl::op,SegMaxSubarray_impl::e>{
    using S=SegMaxSubarray_impl::S;
    using Base=SegBase<S,SegMaxSubarray_impl::op,SegMaxSubarray_impl::e>;
    using Base::Base; using Base::set;
    static vector<S> cv(const vector<ll>&a){vector<S>v;v.reserve(a.size());for(ll x:a)v.pb(SegMaxSubarray_impl::gen(x));return v;}
    SegMaxSubarray(const vector<ll>&a):Base(cv(a)){}
    void set(int i,ll x){Base::set(i,SegMaxSubarray_impl::gen(x));}
};

namespace SegAffine_impl{
    struct S{
        mint a,b;
        mint eval(mint x)const{return a*x+b;}
    };
    S op(S f,S g){return {g.a*f.a,g.a*f.b+g.b};}
    S e(){return {1,0};}
}
struct SegAffine:SegBase<SegAffine_impl::S,SegAffine_impl::op,SegAffine_impl::e>{
    using S=SegAffine_impl::S;
    using Base=SegBase<S,SegAffine_impl::op,SegAffine_impl::e>;
    using Base::Base;
};

namespace SegBracket_impl{
    struct S{ll sum,mn;};
    S gen(char c){return c=='('?S{1,0}:S{-1,-1};}
    S op(S a,S b){return {a.sum+b.sum,min(a.mn,a.sum+b.mn)};}
    S e(){return {0,0};}
}
struct SegBracket:SegBase<SegBracket_impl::S,SegBracket_impl::op,SegBracket_impl::e>{
    using S=SegBracket_impl::S;
    using Base=SegBase<S,SegBracket_impl::op,SegBracket_impl::e>;
    using Base::Base; using Base::set;
    static vector<S> cv(const string&s){vector<S>v;v.reserve(s.size());for(char c:s)v.pb(SegBracket_impl::gen(c));return v;}
    SegBracket(const string&s):Base(cv(s)){}
    void set(int i,char c){Base::set(i,SegBracket_impl::gen(c));}
    bool valid(int l,int r){auto x=Base::prod(l,r);return x.sum==0&&x.mn>=0;}
};
/*
汎用セグ木テンプレ





/*
SegArgMax seg(v) 区間最大値とその最左位置を管理 O(N)
pair相当 seg.prod(l,r) {最大値,その最左index}を返す O(logN)
void seg.set(i,x) A[i]=xに更新 O(logN)
SegArgMin seg(v) 区間最小値とその最左位置を管理 O(N)
pair相当 seg.prod(l,r) {最小値,その最左index}を返す O(logN)
void seg.set(i,x) A[i]=xに更新 O(logN)

SegMaxSubarray seg(v) 動的な最大部分配列和を管理、空部分列は不可 O(N)
S seg.prod(l,r) {sum,pref,suff,best}を返す O(logN)
void seg.set(i,x) A[i]=xに更新 O(logN)

SegAffine seg(v) 一次関数f(x)=ax+bの列を合成して管理 O(N)
S seg.prod(l,r) f[r-1]∘...∘f[l]を{a,b}で返す O(logN)
mint seg.prod(l,r).eval(x) 区間の合成関数をxに適用 O(logN)

SegBracket seg(s) 括弧列を構築 O(N)
S seg.prod(l,r) [l,r)の{総和,最小prefix和}を返す O(logN)
bool seg.valid(l,r) [l,r)が正しい括弧列か判定 O(logN)
void seg.set(i,c) i番目を'('または')'に更新 O(logN)

SegMinMax::S={mx,mn}
SegArgMax::S / SegArgMin::S={val,id}
SegMaxSubarray::S={sum,pref,suff,best}
SegAffine::S={a,b}
SegBracket::S={sum,mn}
区間はすべて[l,r)

void seg.set(i,x) i番目をxに更新 O(logN)
S seg.get(i) i番目の値を返す O(1)
S seg.prod(l,r) [l,r)の集約値を返す O(logN)
S seg.all_prod() 全区間の集約値を返す O(1)
int seg.max_right<f>(l) f(prod(l,r))を満たす最大rを返す O(logN)
int seg.min_left<f>(r) f(prod(l,r))を満たす最小lを返す O(logN)

SegMax seg(v) 区間最大値を管理 O(N)
SegMin seg(v) 区間最小値を管理 O(N)
SegSum seg(v) 区間和を管理 O(N)
SegXOR seg(v) 区間XORを管理 O(N)
SegOR seg(v)  区間ORを管理 O(N)
SegAND seg(v) 区間ANDを管理 O(N)
SegGCD seg(v) 区間GCDを管理 O(N)
SegMinMax seg(v) 区間最大値・最小値を同時管理 O(N)
*/

namespace SegXXX {
    struct S{
        ll left;
        ll right;
    };// 情報

    S op(S a,S b){
    S ret = {0,0};
        ret.left += a.left;
        ret.right += b.right;
        if(a.right > b.left) ret.right += a.right-b.left;
        if(a.right < b.left) ret.left += b.left-a.right;

        return ret;
    }// merge

    S e(){
        return {
            0LL,0LL
        };
    }// 単位元

    using Seg=segtree<S,op,e>;
}

//vector<SegXXX::S> v(n);
//SegXXX::Seg seg(v);
signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    

    ll n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<SegXXX::S> v(n);
    rep(i,n){
        if(s[i] == '(') v[i] = {0,1};
        else v[i] = {1,0};
    }

    SegXXX::Seg seg(v);
    rep(i,q){
        ll type, x, y;
        cin >> type >> x >> y;
        if(type == 1){
            x--;
            if(y == 1) seg.set(x,{0,1});
            else seg.set(x,{1,0});
        }
        else{
            ll ans = y-x+1;
            auto a = seg.prod(x-1,y);
            ans -= a.left+a.right;
            p(ans);

        }
    }

}