結果
問題 | No.1802 Range Score Query for Bracket Sequence |
ユーザー |
![]() |
提出日時 | 2022-01-07 21:35:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 435 ms / 2,000 ms |
コード長 | 756 bytes |
コンパイル時間 | 4,064 ms |
コンパイル使用メモリ | 253,004 KB |
最終ジャッジ日時 | 2025-01-27 09:16:28 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint1000000007; using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define Inf 1000000001 int main(){ int n,q; cin>>n>>q; string s; cin>>s; fenwick_tree<int> F(n); rep(i,n-1){ if(s[i]=='('&&s[i+1]==')')F.add(i,1); } rep(_,q){ int t; cin>>t; if(t==1){ int x; cin>>x; x--; if(s[x]=='(')s[x] = ')'; else s[x] = '('; for(int i=x-1;i<=x;i++){ if(i<0||i>=n-1)continue; F.add(i,-F.sum(i,i+1)); if(s[i]=='('&&s[i+1]==')')F.add(i,1); } } else{ int l,r; cin>>l>>r; if(l==r){ cout<<0<<endl; continue; } l--; r--; cout<<F.sum(l,r)<<endl; } } return 0; }