結果
問題 | No.875 Range Mindex Query |
ユーザー | kept1994 |
提出日時 | 2022-01-06 00:51:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 783 ms / 2,000 ms |
コード長 | 3,277 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 124,328 KB |
最終ジャッジ日時 | 2024-04-24 05:21:53 |
合計ジャッジ時間 | 8,647 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 110 ms
105,728 KB |
testcase_01 | AC | 129 ms
106,112 KB |
testcase_02 | AC | 158 ms
110,904 KB |
testcase_03 | AC | 110 ms
106,128 KB |
testcase_04 | AC | 120 ms
106,048 KB |
testcase_05 | AC | 114 ms
105,776 KB |
testcase_06 | AC | 126 ms
105,508 KB |
testcase_07 | AC | 134 ms
105,984 KB |
testcase_08 | AC | 118 ms
105,724 KB |
testcase_09 | AC | 124 ms
105,900 KB |
testcase_10 | AC | 156 ms
111,000 KB |
testcase_11 | AC | 745 ms
123,728 KB |
testcase_12 | AC | 607 ms
120,360 KB |
testcase_13 | AC | 632 ms
122,264 KB |
testcase_14 | AC | 650 ms
121,592 KB |
testcase_15 | AC | 783 ms
124,328 KB |
testcase_16 | AC | 733 ms
119,924 KB |
testcase_17 | AC | 768 ms
120,092 KB |
testcase_18 | AC | 727 ms
120,464 KB |
ソースコード
#!/usr/bin/env python3 class SegmentTree: def __init__(self, monoid: int, bottomLen: int, operation: "function"): self.monoid = monoid self.bottomLen = bottomLen self.offset = self.bottomLen # セグ木の最下層の最初のインデックスに合わせるためのオフセット self.segLen = self.bottomLen * 2 self.tree = [monoid] * self.bottomLen + [[i, monoid] for i in range(self.bottomLen)] # 最下層以外はインデックスのない配列を初期値にしているが、のちにallBuild()するのであれば問題ない。 self.operation = operation return """ 1点取得 O(1) """ def getPoint(self, index: int): segIndex = index + self.offset return self.tree[segIndex] """ 1点更新 O(1) """ def pointUpdateWithoutRebuild(self, index: int, val: int): segIndex = index + self.offset self.tree[segIndex] = [index, val] # 各マスの更新方法 return """ 全区間更新 O(bottomLen) # =セグ木の配列長 """ def allBuild(self): for segIndex in reversed(range(self.offset)): if segIndex == 0: return self.tree[segIndex] = self.operation(self.tree[segIndex * 2], self.tree[segIndex * 2 + 1]) return """ 1点更新 + リビルド O(log(bottomLen)) """ def pointUpdate(self, index: int, val: int): segIndex = index + self.offset self.tree[segIndex] = [index, val] # 各マスの更新方法 while True: segIndex //= 2 if segIndex == 0: break self.tree[segIndex] = self.operation(self.tree[segIndex * 2], self.tree[segIndex * 2 + 1]) return """ 1点更新 + リビルド O(log(bottomLen)) """ def rangeQuery(self, l: int, r: int): l += self.offset r += self.offset res = [0, self.monoid] # クエリの初期値 while l < r: if l % 2 == 1: res = self.operation(res, self.tree[l]) l += 1 l //= 2 if r % 2 == 1: res = self.operation(res, self.tree[r - 1]) r -= 1 r //= 2 return res def minWithIndex(a: "list[val, index]", b: "list[val, index]"): # print("minWithIndex", a, b) return a if a[1] < b[1] else b def main(): INF = 10 ** 6 N, Q = map(int, input().split()) A = list(map(int, input().split())) tr = SegmentTree(monoid=INF, bottomLen=2**18, operation=minWithIndex) for i in range(N): tr.pointUpdateWithoutRebuild(i, A[i]) tr.allBuild() for i in range(Q): t, l, r = map(int, input().split()) if t == 1: # l - 1 と r - 1 のSWAP al, ar = tr.getPoint(l - 1), tr.getPoint(r - 1) tr.pointUpdate(l - 1, ar[1]) tr.pointUpdate(r - 1, al[1]) # print(tr.tree) else: # l - 1 〜 r - 1 の区間の最小値を与えるインデックスを出力。 i, _ = tr.rangeQuery(l - 1, r) print(i + 1) # print(tr.tree) return if __name__ == '__main__': main()