結果

問題 No.3198 Monotonic Query
ユーザー miztom
提出日時 2025-07-11 21:37:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 566 ms / 3,000 ms
コード長 1,103 bytes
コンパイル時間 897 ms
コンパイル使用メモリ 82,204 KB
実行使用メモリ 83,376 KB
最終ジャッジ日時 2025-07-12 10:53:06
合計ジャッジ時間 13,133 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegTree:
    def __init__(self,func,unit,array):
        if type(array)==int:n=array;array=[unit]*n
        else:n=len(array)
        self.func=func
        self.unit=unit
        self.num=1<<(n-1).bit_length()
        self.tree=[unit]*2*self.num
        for i in range(n):
            self.tree[self.num+i]=array[i]
        for i in range(self.num-1,0,-1):
            self.tree[i]=self.func(self.tree[2*i],self.tree[2*i+1])
    def get(self,i):return self.tree[i+self.num]
    def set(self,i,x):
        i+=self.num
        self.tree[i]=x
        while i>1:
            self.tree[i>>1]=self.func(self.tree[i],self.tree[i^1])
            i>>=1
    def prod(self,l,r):
        a=self.unit
        l+=self.num
        r+=self.num
        while l<r:
            if l&1:
                a=self.func(a,self.tree[l])
                l+=1
            if r&1:
                a=self.func(a,self.tree[r-1])
            l>>=1
            r>>=1
        return a
s=SegTree(max,p:=0,q:=int(input()))
for i in range(q):
    q,x=map(int,input().split())
    if q==1:s.set(p,x);p+=1
    else:print(s.prod(p-x,p))
0