結果
問題 |
No.1802 Range Score Query for Bracket Sequence
|
ユーザー |
![]() |
提出日時 | 2023-05-28 23:11:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 371 ms / 2,000 ms |
コード長 | 1,573 bytes |
コンパイル時間 | 887 ms |
コンパイル使用メモリ | 108,988 KB |
最終ジャッジ日時 | 2025-02-13 15:57:51 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <map> #include <set> #include <iomanip> #include <queue> #include <algorithm> #include <numeric> #include <deque> #include <complex> using namespace std; using ll = long long; //RSQ (0-indexed) template<class T> struct BIT { vector<T> bit; int N; BIT (int n){ N = n; bit.resize(N); } void add(int loc, T val){ loc++; while(loc <= N){ bit[loc-1] += val; loc += loc & -loc; } } T sum(int l, int r){ T res = _sum(r) - _sum(l-1); return res; } T _sum(int r){ r++; T res = 0; while(r > 0){ res += bit[r-1]; r -= r & -r; } return res; } }; int main(){ int N, Q, l, r, t; string S; cin >> N >> Q >> S; BIT<int> tree(N-1); for (int i=0; i<N-1; i++){ if (S[i] == '(' && S[i+1] == ')') tree.add(i, 1); } for (int i=0; i<Q; i++){ cin >> t; if (t == 1){ cin >> l; l--; if (l-1>=0 && S[l-1] == '(' && S[l] == ')') tree.add(l-1, -1); else if (l-1>=0 && S[l-1] == '(' && S[l] == '(') tree.add(l-1, 1); if (l+1<=N-1 && S[l] == '(' && S[l+1] == ')') tree.add(l, -1); else if (l+1<=N-1 && S[l] == ')' && S[l+1] == ')') tree.add(l, 1); S[l] = '('+')'-S[l]; } else{ cin >> l >> r; l--; r--; cout << tree.sum(l, r-1) << endl; } } return 0; }