結果
問題 | No.1802 Range Score Query for Bracket Sequence |
ユーザー |
👑 ![]() |
提出日時 | 2022-01-07 21:56:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 540 ms / 2,000 ms |
コード長 | 4,260 bytes |
コンパイル時間 | 120 ms |
コンパイル使用メモリ | 82,168 KB |
実行使用メモリ | 110,592 KB |
最終ジャッジ日時 | 2024-06-30 02:14:37 |
合計ジャッジ時間 | 9,023 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
class Binary_Indexed_Tree():def __init__(self, L, calc, unit, inv, index=1):""" calc を演算とする N 項の Binary Indexed Tree を作成calc: 演算 (2変数関数, 可換群)unit: 群 calc の単位元 (x+e=e+x=xを満たすe)inv : 群 calc の逆元 (1変数関数, x+y(x)=y(x)+x=e をみたす y(x))"""self.calc=calcself.unit=unitself.inv=invself.index=indexN=len(L)d=max(1,(N-1).bit_length())k=2**dX=[None]+[unit]*kself.num=kself.depth=dif L:for i in range(len(L)):p=i+1while p<=k:X[p]=self.calc(X[p],L[i])p+=p&(-p)self.data=Xdef index_number(self, k, index=1):""" 第 k 要素の値を出力する.k : 数列の要素index: 先頭の要素の番号"""return self.sum(k,k,index)def add(self, k, x, index=1):""" 第 k 要素に x を加え, 更新を行う.k : 数列の要素x : 加える値index: 先頭の要素の番号"""p=k+(1-index)while p<=self.num:self.data[p]=self.calc(self.data[p],x)p+=p&(-p)def update(self, k, x, index=1):""" 第 k 要素を x に変え, 更新を行う.k: 数列の要素x: 更新後の値"""a=self.index_number(k,index)y=self.calc(self.inv(a),x)self.add(k,y,index)def sum(self, From, To, index=1):""" 第 From 要素から第 To 要素までの総和を求める.※From!=1を使うならば, 群でなくてはならない.From : 始まりTo : 終わりindex: 先頭の要素の番号"""alpha=max(1,From+(1-index))beta=min(self.num,To+(1-index))if alpha>beta:return self.unitelif alpha==1:return self.__section(beta)else:return self.calc(self.inv(self.__section(alpha-1)),self.__section(beta))def __section(self,x):""" B[1]+...+B[x] を求める. """S=self.unitwhile x>0:S=self.calc(self.data[x],S)x-=x&(-x)return Sdef all_sum(self):return self.data[-1]def binary_search(self, cond, index=1):""" cond(B[1]+...+B[k]) を満たす最小の k を返す.cond: 単調増加※ cond(unit)=True の場合の返り値は index-1※ cond(B[1]+...+B[k]) なる k が存在しない場合の返り値は self.num+index"""if cond(self.unit):return index-1j=0r=self.numt=rdata=self.dataalpha=self.unitfor _ in range(self.depth+1):if j+t<=self.num:beta=self.calc(alpha,data[j+t])if not cond(beta):alpha=betaj+=tt>>=1return j+indexdef __getitem__(self,index):if isinstance(index,int):return self.index_number(index,self.index)else:return [self.index_number(t,self.index) for t in index]def __setitem__(self,index,val):self.update(index,val,self.index)#==================================================from operator import add,negimport sysinput=sys.stdin.readlinewrite=sys.stdout.writeN,Q=map(int,input().split())S=["*"]+list(input())B=Binary_Indexed_Tree([0]*(N-1),add,0,neg,1)for i in range(1,N):if S[i]=="(" and S[i+1]==")":B.add(i,1,1)Ans=[]for _ in range(Q):type,*A=map(int,input().split())if type==1:i,=Aif S[i]==")":S[i]="("else:S[i]=")"if i>1:if S[i-1]=="(" and S[i]==")":B.update(i-1,1,1)else:B.update(i-1,0,1)if i<N:if S[i]=="(" and S[i+1]==")":B.update(i,1,1)else:B.update(i,0,1)else:l,r=AAns.append(B.sum(l,r-1,1))write("\n".join(map(str,Ans)))