結果

問題 No.1802 Range Score Query for Bracket Sequence
ユーザー 👑 Kazun
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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=xe)
inv : calc (1, x+y(x)=y(x)+x=e y(x))
"""
self.calc=calc
self.unit=unit
self.inv=inv
self.index=index
N=len(L)
d=max(1,(N-1).bit_length())
k=2**d
X=[None]+[unit]*k
self.num=k
self.depth=d
if L:
for i in range(len(L)):
p=i+1
while p<=k:
X[p]=self.calc(X[p],L[i])
p+=p&(-p)
self.data=X
def 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.unit
elif 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.unit
while x>0:
S=self.calc(self.data[x],S)
x-=x&(-x)
return S
def 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-1
j=0
r=self.num
t=r
data=self.data
alpha=self.unit
for _ in range(self.depth+1):
if j+t<=self.num:
beta=self.calc(alpha,data[j+t])
if not cond(beta):
alpha=beta
j+=t
t>>=1
return j+index
def __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,neg
import sys
input=sys.stdin.readline
write=sys.stdout.write
N,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,=A
if 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=A
Ans.append(B.sum(l,r-1,1))
write("\n".join(map(str,Ans)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0