結果

問題 No.8121 [Deleted]
コンテスト
ユーザー Koi
提出日時 2025-04-01 22:54:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,085 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 105,400 KB
最終ジャッジ日時 2025-04-01 22:54:22
合計ジャッジ時間 6,328 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class SegTree:
    def __init__(self,N,A,op,e) -> None:
        #N:数列の長さ
        #A:数列の初期状態
        #op:区間で答えたいもの
        #e:∀a,op(a,e)=aとなる単位元e
        size=1
        log_size=1
        while size<N:
            size*=2
            log_size+=1
        #size:セグ木の横の大きさ
        #log_size:セグ木の深さ
        self.size=size
        self.log_size=log_size
        self.op=op
        self.e=e
        self.tree=[e]*(2*size)
        for i in range(N):
            self.tree[size+i]=A[i]
        for i in range((size-1),0,-1):
            self.tree[i]=op(self.tree[2*i],self.tree[2*i+1])
        #treeの0番目の値は使用しない(欠番)
    
    #seg_treeを深さ順に出力
    #時間計算量O(N)
    def print_seg_tree(self):
        for i in range(self.log_size):
            print(self.tree[2**i:2**(i+1)])

    #Aのi番目(0-indexed)の要素を取得
    #時間計算量O(1)
    def get(self,i):
        return self.tree[self.size+i]

    #Aのi番目(0-indexed)の要素をxに変更
    #時間計算量O(logN)
    def update(self,i,x):
        i+=self.size
        self.tree[i]=x
        while i>1:
            i=i//2
            self.tree[i]=self.op(self.tree[2*i],self.tree[2*i+1])
            
    #Aの[l,r)に対するopを取得(0-indexed)
    def range_op(self,l,r):
        l+=self.size
        r+=self.size
        left_result=self.e
        right_result=self.e
        while l<r:
            if(l%2==1):
                left_result=self.op(left_result,self.tree[l])
                l+=1
            if(r%2==1):
                right_result=self.op(right_result,self.tree[r-1])
                r-=1
            l=l//2
            r=r//2
        return self.op(left_result,right_result)

N,Q=map(int,input().split())
A=list(map(int, input().split()))
ST=SegTree(N,A,max,-1)
Ans = []
for i in range(Q):
    r, a, b = map(int, input().split())
    if(r == 2):
        Ans.append(ST.range_op(a - 1, b))
    else:
        ST.update(a - 1, ST.get(a - 1) + b)
for x in Ans:
    print(x)
0