結果
問題 | No.1802 Range Score Query for Bracket Sequence |
ユーザー |
![]() |
提出日時 | 2022-01-07 21:47:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 457 ms / 2,000 ms |
コード長 | 2,188 bytes |
コンパイル時間 | 2,003 ms |
コンパイル使用メモリ | 195,360 KB |
最終ジャッジ日時 | 2025-01-27 09:20:50 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <typename T> struct BinaryIndexedTree { int N; vector<T>bit; BinaryIndexedTree(){} BinaryIndexedTree(int x) { N = x; bit.resize(x+1); } void add(int x,T y) { while(x <= N) { bit[x] += y; x += x&-x; } } T sum(int x) { T res = 0; while(x) { res += bit[x]; x -= x&-x; } return res; } inline T sum(int l, int r) {//[l,r] return sum(r)-sum(l-1); } inline T operator[](int k) { return sum(k)-sum(k-1); } int lower_bound(T w) {// left sum(i) >= w int x = 0; for (int k = 1 << __lg(N); k; k >>= 1) { if (x + k <= N - 1 && bit[x + k] < w) { w -= bit[x + k]; x += k; } } return x; } int upper_bound(T w) {// left sum(i) > w int x = 0; for (int k = 1 << __lg(N); k; k >>= 1) { if (x + k <= N - 1 && bit[x + k] <= w) { w -= bit[x + k]; x += k; } } return x; } }; int main() { int N,Q; string S; cin >> N >> Q >> S; BinaryIndexedTree<int>bit(N); for(int i = 0; i+1 < N; i++) { if(S[i] == '(' && S[i+1] == ')') { bit.add(i+1,1); } } while (Q--) { int f; cin >> f; if(f == 1) { int a; cin >> a; a--; if(S[a] == '(') { if(a+1 < N && S[a+1] == ')') { bit.add(a+1,-1); } if(a && S[a-1] == '(') { bit.add(a,1); } S[a] = ')'; } else { if(a+1 < N && S[a+1] == ')') { bit.add(a+1,1); } if(a && S[a-1] == '(') { bit.add(a,-1); } S[a] = '('; } } else { int l,r; cin >> l >> r; cout << bit.sum(l,r-1) << endl; } } }