結果
問題 | No.875 Range Mindex Query |
ユーザー | lloyz |
提出日時 | 2022-06-27 23:20:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 587 ms / 2,000 ms |
コード長 | 4,359 bytes |
コンパイル時間 | 183 ms |
コンパイル使用メモリ | 82,592 KB |
実行使用メモリ | 108,392 KB |
最終ジャッジ日時 | 2024-04-30 12:17:48 |
合計ジャッジ時間 | 7,307 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
55,744 KB |
testcase_01 | AC | 68 ms
68,316 KB |
testcase_02 | AC | 82 ms
72,256 KB |
testcase_03 | AC | 54 ms
62,484 KB |
testcase_04 | AC | 58 ms
64,228 KB |
testcase_05 | AC | 48 ms
55,972 KB |
testcase_06 | AC | 65 ms
67,408 KB |
testcase_07 | AC | 72 ms
70,436 KB |
testcase_08 | AC | 58 ms
65,040 KB |
testcase_09 | AC | 58 ms
64,760 KB |
testcase_10 | AC | 78 ms
72,892 KB |
testcase_11 | AC | 587 ms
101,236 KB |
testcase_12 | AC | 520 ms
92,508 KB |
testcase_13 | AC | 495 ms
107,804 KB |
testcase_14 | AC | 483 ms
104,460 KB |
testcase_15 | AC | 572 ms
107,948 KB |
testcase_16 | AC | 541 ms
107,632 KB |
testcase_17 | AC | 569 ms
108,080 KB |
testcase_18 | AC | 567 ms
108,392 KB |
ソースコード
class SegmentTree: __all__ = ['setval', 'pointupdate', 'segquery', 'segsearch_right', 'pointgetval'] def __init__(self, n=10**6, idetify_elt=-10**9, func=max): assert (func(idetify_elt, idetify_elt) == idetify_elt) self._n = n self._seg_length_half = 2**(n-1).bit_length() self._idetify_elt = idetify_elt self._seg = [idetify_elt]*(2*self._seg_length_half) self._func = func def setval(self, x_list): '''Set value : A = x_list''' assert (len(x_list) == self._n) # Set value at the bottom for i in range(self._n): self._seg[i+self._seg_length_half-1] = x_list[i] # Build value for i in range(self._seg_length_half-2, -1, -1): self._seg[i] = self._func(self._seg[2*i+1], self._seg[2*i+2]) def pointupdate(self, k, x): '''Update : A[k] = x ''' pos = k + self._seg_length_half - 1 # Set value at k-th self._seg[pos] = x # Build bottom-up while pos: pos = (pos-1)//2 self._seg[pos] = self._func(self._seg[pos*2+1], self._seg[pos*2+2]) def pointgetval(self, k): ''' Return A[k] ''' return self._seg[k + self._seg_length_half - 1] def segquery(self, left, right): ''' Return func(A[left], ... , A[right-1]) ''' # if not left < right if right <= left: return self._idetify_elt func_value = self._idetify_elt leftpos = left + self._seg_length_half - 1 # leftmost segment rightpos = right + self._seg_length_half - 2 # rightmost segment while leftpos < rightpos-1: if leftpos&1 == 0: # if leftpos is right-child func_value = self._func(func_value, self._seg[leftpos]) if rightpos&1 == 1: # if rightpos is leftchild func_value = self._func(func_value, self._seg[rightpos]) rightpos -= 1 # move up leftpos = leftpos//2 rightpos = (rightpos-1)//2 func_value = self._func(func_value, self._seg[leftpos]) if leftpos != rightpos: func_value = self._func(func_value, self._seg[rightpos]) return func_value def segsearch_right(self, condfunc, left=0): ''' Return min_i satisfying condfunc( func( A[left], ... , A[i])) if impossible : return n ''' # if impossible (ie. condfunc( func( A[left], ... , A[-1])) is False) if not condfunc(self._segquery(left, self._n)): return self._n # possible func_value = self._idetify_elt rightpos = left + self._seg_length_half - 1 while True: # while rightpos is the left-child, move bottom-up while rightpos&1 == 1: rightpos //= 2 # try up_value_trial = self._func(func_value, self._seg[rightpos]) if not condfunc(up_value_trial): # move up and right func_value = up_value_trial rightpos = (rightpos-1)//2 + 1 else: # move top-down while rightpos < self._seg_length_half-1: down_value_trial = self._func(func_value, self._seg[rightpos*2 + 1]) if condfunc(down_value_trial): # move left-child rightpos = rightpos*2 + 1 else: # move right-child func_value = down_value_trial rightpos = rightpos*2 + 2 return rightpos - self._seg_length_half + 1 from collections import defaultdict n, q = map(int, input().split()) A = list(map(int, input().split())) segtree = SegmentTree(n, 10**9, min) segtree.setval(A) val_to_idx = defaultdict(int) for i in range(n): val_to_idx[A[i]] = i + 1 for _ in range(q): d, l, r = map(int, input().split()) if d == 1: l -= 1 r -= 1 pl, pr = segtree.pointgetval(l), segtree.pointgetval(r) segtree.pointupdate(l, pr) segtree.pointupdate(r, pl) val_to_idx[pl] = r + 1 val_to_idx[pr] = l + 1 else: val = segtree.segquery(l - 1, r) print(val_to_idx[val])