結果

問題 No.1802 Range Score Query for Bracket Sequence
ユーザー nawawannawawan
提出日時 2022-01-07 23:58:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 411 ms / 2,000 ms
コード長 2,014 bytes
コンパイル時間 2,377 ms
コンパイル使用メモリ 202,000 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-12 14:15:20
合計ジャッジ時間 8,012 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 274 ms
4,376 KB
testcase_02 AC 275 ms
4,376 KB
testcase_03 AC 275 ms
4,380 KB
testcase_04 AC 274 ms
4,380 KB
testcase_05 AC 275 ms
4,376 KB
testcase_06 AC 274 ms
4,380 KB
testcase_07 AC 277 ms
4,376 KB
testcase_08 AC 281 ms
4,376 KB
testcase_09 AC 275 ms
4,376 KB
testcase_10 AC 275 ms
4,376 KB
testcase_11 AC 258 ms
4,380 KB
testcase_12 AC 259 ms
4,376 KB
testcase_13 AC 259 ms
4,376 KB
testcase_14 AC 411 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 2 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

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