結果
問題 |
No.3198 Monotonic Query
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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))