結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー toyuzuko
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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