結果

問題 No.875 Range Mindex Query
ユーザー toyuzukotoyuzuko
提出日時 2020-03-09 01:00:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 431 ms / 2,000 ms
コード長 1,871 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 94,736 KB
最終ジャッジ日時 2024-11-07 20:21:58
合計ジャッジ時間 5,723 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,804 KB
testcase_01 AC 64 ms
67,080 KB
testcase_02 AC 75 ms
71,124 KB
testcase_03 AC 47 ms
60,792 KB
testcase_04 AC 55 ms
62,464 KB
testcase_05 AC 45 ms
59,292 KB
testcase_06 AC 68 ms
66,432 KB
testcase_07 AC 73 ms
68,352 KB
testcase_08 AC 60 ms
63,616 KB
testcase_09 AC 56 ms
62,720 KB
testcase_10 AC 73 ms
71,424 KB
testcase_11 AC 409 ms
90,880 KB
testcase_12 AC 359 ms
86,348 KB
testcase_13 AC 348 ms
94,592 KB
testcase_14 AC 378 ms
92,544 KB
testcase_15 AC 431 ms
94,320 KB
testcase_16 AC 352 ms
94,720 KB
testcase_17 AC 364 ms
94,464 KB
testcase_18 AC 367 ms
94,736 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