結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー nagiss
提出日時 2019-09-07 00:16:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 368 ms / 2,000 ms
コード長 1,828 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 100,428 KB
最終ジャッジ日時 2024-06-24 22:40:48
合計ジャッジ時間 4,553 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op"]
    def __init__(self, a, default, op):
        from math import ceil, log
        real_size = len(a)
        self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        self.default = default
        self.op = op
        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

    def get_value(self, x: int, y: int) -> int:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def set_value(self, i:int, value) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i:int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

N, Q = map(int, input().split())
A = list(map(int, input().split()))
seg = SegmentTree(list(enumerate(A)),
                  (-1, float("inf")),
                  lambda x, y: x if x[1]<y[1] else y)
V = seg.tree
siz = seg.elem_size
Ans = []
for i in range(Q):
    q, l, r = map(int, input().split())
    if q==1:
        l-=1
        r-=1
        (_, al), (_, ar) = V[l+siz], V[r+siz]
        seg.set_value(l, (l, ar))
        seg.set_value(r, (r, al))
    else:
        l-=1
        ami, mi = seg.get_value(l, r)
        Ans.append(ami+1)
print("\n".join(map(str, Ans)))
0