結果
問題 | No.1802 Range Score Query for Bracket Sequence |
ユーザー |
|
提出日時 | 2022-01-07 22:11:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 560 ms / 2,000 ms |
コード長 | 1,088 bytes |
コンパイル時間 | 521 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 90,952 KB |
最終ジャッジ日時 | 2024-06-30 02:16:10 |
合計ジャッジ時間 | 8,946 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
class BIT: def __init__(self,size): self.size = size self.tree = [0] * (size+1) def add(self,i,x): while i <= self.size: self.tree[i] += x i += i & -i return def ac(self,i): res = 0 while i > 0: res += self.tree[i] i -= i & -i return res n,q = map(int,input().split()) s = input() l = [] for i in s: if i == '(': l.append(0) else: l.append(1) bit = BIT(n) for i in range(n-1): if l[i] == 0 and l[i+1] == 1: bit.add(i+1,1) for i in range(q): t = list(map(int,input().split())) if t[0] == 1: ind = t[1]-1 l[ind] = (l[ind]+1)%2 if ind > 0: if l[ind] == 1 and l[ind-1] == 0: bit.add(ind,1) elif l[ind] == l[ind-1] == 0: bit.add(ind,-1) if ind < n-1: if l[ind] == 0 and l[ind+1] == 1: bit.add(ind+1,1) elif l[ind] == l[ind+1] == 1: bit.add(ind+1,-1) else: left,right = t[1],t[2] print(bit.ac(right-1) - bit.ac(left-1))