結果
問題 |
No.1802 Range Score Query for Bracket Sequence
|
ユーザー |
![]() |
提出日時 | 2022-01-07 21:29:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 415 ms / 2,000 ms |
コード長 | 1,657 bytes |
コンパイル時間 | 1,549 ms |
コンパイル使用メモリ | 171,500 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 02:12:00 |
合計ジャッジ時間 | 6,993 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <typename T> struct binary_indexed_tree{ int N; vector<T> BIT; binary_indexed_tree(vector<T> &A){ N = A.size(); BIT = vector<T>(N + 1, 0); for (int i = 0; i < N; i++){ BIT[i + 1] = A[i]; } for (int i = 1; i < N; i++){ if (i + (i & -i) <= N){ BIT[i + (i & -i)] += BIT[i]; } } } void add(int i, T x){ i++; while (i <= N){ BIT[i] += x; i += i & -i; } } T sum(int i){ T ans = 0; while (i > 0){ ans += BIT[i]; i -= i & -i; } return ans; } T sum(int L, int R){ return sum(R) - sum(L); } }; int main(){ int N, Q; cin >> N >> Q; string S; cin >> S; vector<int> A(N - 1, 0); for (int i = 0; i < N - 1; i++){ if (S[i] == '(' && S[i + 1] == ')'){ A[i]++; } } binary_indexed_tree<int> BIT(A); for (int j = 0; j < Q; j++){ int t; cin >> t; if (t == 1){ int i; cin >> i; i--; if (i > 0){ if (S[i - 1] == '(' && S[i] == ')'){ BIT.add(i - 1, -1); } } if (i < N - 1){ if (S[i] == '(' && S[i + 1] == ')'){ BIT.add(i, -1); } } if (S[i] == '('){ S[i] = ')'; } else { S[i] = '('; } if (i > 0){ if (S[i - 1] == '(' && S[i] == ')'){ BIT.add(i - 1, 1); } } if (i < N - 1){ if (S[i] == '(' && S[i + 1] == ')'){ BIT.add(i, 1); } } } if (t == 2){ int l, r; cin >> l >> r; l--; cout << BIT.sum(l, r - 1) << endl; } } }