結果

問題 No.3198 Monotonic Query
コンテスト
ユーザー Koi
提出日時 2025-07-11 21:52:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 502 ms / 3,000 ms
コード長 2,016 bytes
コンパイル時間 565 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 83,236 KB
最終ジャッジ日時 2025-07-12 10:53:51
合計ジャッジ時間 11,889 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)

Q = int(input())
ST = SegTree(Q, [0] * Q, max, 0)
ind = 0
for _ in range(Q):
    r, v = map(int, input().split())
    if(r == 1):
        ST.update(ind, v)
        ind += 1
    else:
        print(ST.range_op(ind - v, ind))
0