結果

問題 No.3652 Range Bracket Sequence
コンテスト
ユーザー とある理系大学生の日常
提出日時 2026-07-30 11:51:57
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,566 ms / 2,000 ms
+ 348µs
コード長 3,120 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 240 ms
コンパイル使用メモリ 95,976 KB
実行使用メモリ 129,152 KB
最終ジャッジ日時 2026-08-28 21:13:05
合計ジャッジ時間 44,593 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class Lazy_Segment_Tree:#区間加算
    def __init__(self,N:int,A:list):
        if A is None:
            A=[]
        self.A=[0]*(2<<N)
        self.Lazy=[0]*(2<<N)
        self.N=N
        self.L=[0]*(2<<N)
        self.R=[(1<<N)-1]*(2<<N)
        for n in range(1,1<<N):
            self.L[2*n]=self.L[n]
            self.R[2*n]=(self.L[n]+self.R[n])//2
            self.L[2*n+1]=(self.L[n]+self.R[n])//2+1
            self.R[2*n+1]=self.R[n]
        self.ZERO=float("inf")
        for a in range(len(A)):
            self.A[(1<<N)+a]=A[a]
        for n in range((1<<self.N)-1,0,-1):
            self.A[n]=self.F(self.A[2*n]+self.Lazy[2*n],self.A[2*n+1]+self.Lazy[2*n+1])

    def add(self,L:int,R:int,X:int):
        STACK=[[L,R,X,1]]
        RE=[]
        while len(STACK):
            l,r,x,n=STACK[-1]
            STACK.pop()
            if l==self.L[n] and r==self.R[n]:
                self.Lazy[n]+=x
                continue
            elif r<=self.R[n*2]:
                STACK.append([l,r,x,n*2])
            elif self.L[n*2+1]<=l:
                STACK.append([l,r,x,n*2+1])
            else:
                STACK.append([l,self.R[n*2],x,n*2])
                STACK.append([self.L[n*2+1],r,x,n*2+1])
            RE.append(n)
        for a in range(len(RE)):
            n=RE[-a-1]
            self.A[n]=self.F(self.A[2*n]+self.Lazy[2*n],self.A[2*n+1]+self.Lazy[2*n+1])

    def F(self,a,b):#ここをいじることでminとmaxを切り替えることができる
        return min(a,b)

    def query(self,L:int,R:int):
        STACK=[[L,R,1]]
        RE=[]
        ANS=self.ZERO
        while len(STACK):
            l,r,n=STACK[-1]
            STACK.pop()
            if l==self.L[n] and r==self.R[n]:
                ANS=self.F(ANS,self.A[n]+self.Lazy[n])
                continue
            elif r<=self.R[n*2]:
                STACK.append([l,r,n*2])
            elif self.L[n*2+1]<=l:
                STACK.append([l,r,n*2+1])
            else:
                STACK.append([l,self.R[n*2],n*2])
                STACK.append([self.L[n*2+1],r,n*2+1])
            if self.Lazy[n]!=0:
                self.Lazy[2*n]+=self.Lazy[n]
                self.Lazy[2*n+1]+=self.Lazy[n]
                self.Lazy[n]=0
            RE.append(n)
        for a in range(len(RE)):
            n=RE[-a-1]
            self.A[n]=self.F(self.A[2*n]+self.Lazy[2*n],self.A[2*n+1]+self.Lazy[2*n+1])
        return ANS
N,Q=map(int,input().split())
S=input()
A=[]
D=[]
B=0
for n in range(N):
    if S[n]=="(":
        B+=1
        D.append(1)
    else:
        D.append(2)
        B-=1
    A.append(B)

C=Lazy_Segment_Tree(18,A)
for q in range(Q):
    A=list(map(int,input().split()))
    if A[0]==1:
        if A[2]==1:
            if D[A[1]-1]==2:
                C.add(A[1]-1,N,2)
                D[A[1]-1]=1
        else:
            if D[A[1]-1]==1:
                C.add(A[1]-1,N,-2)
                D[A[1]-1]=2
    else:
        if A[1] == 1:
            a = 0
        else:
            a = C.query(A[1]-1-1,A[1]-1-1)

        print((A[2]-A[1]+1)-((C.query(A[2]-1,A[2]-1))-a)-2*(max(0,a-C.query(A[1]-1, A[2]-1))))
0