結果

問題 No.875 Range Mindex Query
ユーザー toyuzukotoyuzuko
提出日時 2020-03-09 01:00:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 504 ms / 2,000 ms
コード長 1,871 bytes
コンパイル時間 585 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 95,104 KB
最終ジャッジ日時 2024-04-25 09:46:51
合計ジャッジ時間 6,509 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
52,224 KB
testcase_01 AC 70 ms
67,072 KB
testcase_02 AC 89 ms
71,424 KB
testcase_03 AC 52 ms
59,648 KB
testcase_04 AC 61 ms
62,848 KB
testcase_05 AC 51 ms
59,136 KB
testcase_06 AC 69 ms
66,432 KB
testcase_07 AC 78 ms
67,968 KB
testcase_08 AC 62 ms
63,744 KB
testcase_09 AC 60 ms
62,976 KB
testcase_10 AC 85 ms
71,424 KB
testcase_11 AC 504 ms
90,624 KB
testcase_12 AC 429 ms
86,304 KB
testcase_13 AC 399 ms
94,464 KB
testcase_14 AC 417 ms
92,544 KB
testcase_15 AC 479 ms
94,976 KB
testcase_16 AC 428 ms
95,104 KB
testcase_17 AC 449 ms
95,104 KB
testcase_18 AC 446 ms
94,720 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.n = 2**(len(arr) - 1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i - 1] = arr[i]
        for i in range(self.n - 1)[::-1]:
            self.tree[i] = func(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def set(self, index, x):
        index += self.n - 1
        self.tree[index] = x
        while index:
            index = (index - 1) // 2
            self.tree[index] = self.func(self.tree[2 * index + 1],
                                         self.tree[2 * index + 2])

    def query(self, left, right):
        if right <= left:
            return self.ie
        left += self.n - 1
        right += self.n - 2
        tmp_l = self.ie
        tmp_r = self.ie
        while right - left > 1:
            if left & 1 == 0:
                tmp_l = self.func(tmp_l, self.tree[left])
            if right & 1 == 1:
                tmp_r = self.func(self.tree[right], tmp_r)
                right -= 1
            left = left // 2
            right = (right - 1) // 2
        if left == right:
            tmp_l = self.func(tmp_l, self.tree[left])
        else:
            tmp_l = self.func(
                self.func(tmp_l, self.tree[left]), self.tree[right])
        return self.func(tmp_l, tmp_r)


N, Q = map(int, input().split())
X = list(map(int, input().split()))
A = [(X[i], i + 1) for i in range(N)]

st = SegmentTree(A, min, (2**63, None))
ans = []

for _ in range(Q):
    q, l, r = map(int, input().split())
    if q == 1:
        al = st.query(l - 1, l)[0]
        ar = st.query(r - 1, r)[0]
        st.set(l - 1, (ar, l))
        st.set(r - 1, (al, r))
    else:
        ans.append(st.query(l - 1, r)[1])

print('\n'.join(map(str, ans)))
0