結果

問題 No.1802 Range Score Query for Bracket Sequence
コンテスト
ユーザー nawawan
提出日時 2022-01-07 23:58:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 447 ms / 2,000 ms
コード長 2,014 bytes
コンパイル時間 2,166 ms
コンパイル使用メモリ 198,300 KB
最終ジャッジ日時 2025-01-27 09:49:30
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct BIT{
    vector<T> num;
    int N;
    BIT(int n) : N(n + 1){
        num.resize(N, 0);
    }
    /*
    区間 [l, r)(0-indexed)のsumを知りたいとき
    sum(r) - sum(l);
    */
    T sum(T t){
        long long res = 0;
        assert(t < N);
        while(t > 0){
            res += num.at(t);
            t -= t & -t;
        }
        return res;
    }
    void add(int ind, T t){
        ind++;
        assert(ind < N);
        while(ind < N){
            num[ind] += t;
            ind += ind & -ind;
        }
    }
    T query(int l, int r){
        assert(r < N && l < N);
        return sum(r) - sum(l - 1);
    }
    int lower_bound(T k){//累積和がk以上となる最小のindexを返す
        int ind = 0;
        int beki = 1;
        assert(k >= 0);
        while(beki < N) beki <<= 1;
        for(int i = beki; i > 0; i >>= 1){
            if(ind + i < N && num[ind + i] < k){
                k -= num[ind + i];
                ind += i;
            }
        }
        return ind;
    }
};
int main(){
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    BIT<int> bit(N);
    for(int i = 0; i < N - 1; i++){
        if(S[i] == '(' && S[i + 1] == ')') bit.add(i, 1);
    }
    while(Q--){
        int t;
        cin >> t;
        if(t == 1){
            int s;
            cin >> s;
            s--;
            if(S[s] == '(') {
                S[s] = ')';
                if(s < N - 1 && S[s + 1] == ')') bit.add(s, -1);
                if(s > 0 && S[s - 1] == '(') bit.add(s - 1, 1);
            }
            else {
                S[s] = '(';
                if(s > 0 && S[s - 1] == '(') bit.add(s - 1, -1);
                if(s < N - 1 && S[s + 1] == ')') bit.add(s, 1);
            }
        }
        else{
            int l, r;
            cin >> l >> r;
            int temp = bit.query(l, r);
            if(bit.query(r, r) == 1) temp--;
            cout << temp << endl;
        }
    }
}
0