結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー cologne
提出日時 2025-11-18 15:14:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 429 ms / 2,000 ms
コード長 1,280 bytes
コンパイル時間 408 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 94,504 KB
最終ジャッジ日時 2025-11-18 15:14:47
合計ジャッジ時間 6,189 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math
import sys


def input(): return sys.stdin.readline().rstrip('\n')


class SegTree:
    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.idx = [(float('inf'), float('inf'))]*(2*self.n)

    def set(self, i, x):
        i += self.n
        self.idx[i] = x
        while i > 1:
            i //= 2
            self.idx[i] = min(self.idx[2*i], self.idx[2*i+1])

    def get(self, l, r):
        l += self.n
        r += self.n
        ans = (float('inf'), float('inf'))
        while l < r:
            if l % 2 == 1:
                ans = min(ans, self.idx[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                ans = min(ans, self.idx[r])
            l //= 2
            r //= 2
        return ans


def main():
    n, q = map(int, input().split())
    *a, = map(int, input().split())
    seg = SegTree(n)
    for i in range(n):
        seg.set(i, (a[i], i))

    for _ in range(q):
        t, l, r = map(int, input().split())
        l -= 1
        r -= 1
        if t == 1:
            a[l], a[r] = a[r], a[l]
            seg.set(l, (a[l], l))
            seg.set(r, (a[r], r))
        else:
            print(seg.get(l, r+1)[1]+1)


if __name__ == '__main__':
    main()
0