結果
問題 | 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) >= wint 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) > wint 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;}}}