結果

問題 No.3652 Range Bracket Sequence
コンテスト
ユーザー とある理系大学生の日常
提出日時 2026-07-30 11:53:54
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,708 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 297 ms
コンパイル使用メモリ 95,720 KB
実行使用メモリ 120,960 KB
最終ジャッジ日時 2026-08-28 21:12:38
合計ジャッジ時間 27,727 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class Lazy_segment_tree:#区間加算MIN用
    __slots__=("N","A","Lazy")
    def __init__(self,N:int,A:list):#要素が2^N個の遅延伝播セグ木を作る
        self.A=[0]*(1<<(N+1))
        self.Lazy=[0]*(1<<(N+1))
        self.N=N
        for n in range(len(A)):
            self.A[n+(1<<self.N)]=A[n]
        for n in range((1<<self.N)-1,0,-1):
            self.Update(n)

    def add(self,L:int,R:int,x:int):#[L,R]にx加算する(減算もできる)
        self.add2(L,R,x,1,0)

    def add2(self,L,R,x,n,d):#LからRの現在の地点はnで深さはd
        LL=(n-(1<<d))*((1<<(self.N-d)))
        RL=LL+(1<<(self.N-d))-1
        M=(LL+RL+1)//2
        if L==LL and R==RL:
            self.Lazy[n]+=x
        elif R<=M-1:
            self.Propagate(n)
            self.add2(L,R,x,n*2,d+1)
            self.Update(n)
        elif M<=L:
            self.Propagate(n)
            self.add2(L,R,x,n*2+1,d+1)
            self.Update(n)
        else:
            self.Propagate(n)
            self.add2(L,M-1,x,n*2,d+1)
            self.add2(M,R,x,n*2+1,d+1)
            self.Update(n)

    def Update(self,n):
        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):
        return min(a,b)

    def Propagate(self,n):
        self.Lazy[2*n]+=self.Lazy[n]
        self.Lazy[2*n+1]+=self.Lazy[n]
        self.A[n]+=self.Lazy[n]
        self.Lazy[n]=0

    def query(self,L,R):#[L,R]の区間クエリ
        return self.query2(L,R,1,0)

    def query2(self,L,R,n,d):
        LL=(n-(1<<d))*((1<<(self.N-d)))
        RL=LL+(1<<(self.N-d))-1
        M=(LL+RL+1)//2
        if L==LL and R==RL:
            return self.A[n]+self.Lazy[n]
        elif R<=M-1:
            self.Propagate(n)
            return self.query2(L,R,n*2,d+1)
        elif M<=L:
            self.Propagate(n)
            return self.query2(L,R,n*2+1,d+1)
        else:
            self.Propagate(n)
            return self.F(self.query2(L,M-1,n*2,d+1),self.query2(M,R,n*2+1,d+1))
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