結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー nakario
提出日時 2019-09-06 22:14:37
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,577 bytes
記録
コンパイル時間 269 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2024-06-24 18:42:56
合計ジャッジ時間 2,301 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


from math import ceil, log2
inf = float('inf')
class SegmentTree:
    def __init__(self, lst, _min=min, _max=inf):
        self.n = int(2**ceil(log2(len(lst))))
        self._lst = [_max for _ in range(2 * self.n - 1)]
        self.min = _min
        self.max = _max
        for i, v in enumerate(lst):
            self.update(i, v)

    @property
    def lst(self):
        return self._lst[self.n-1:]

    def update(self, i, v):
        i += self.n - 1
        self._lst[i] = v
        while i > 0:
            i = (i - 1) // 2
            self._lst[i] = self.min(self._lst[i*2+1], self._lst[i*2+2])

    def query(self, a, b):
        return self._query(a, b, 0, 0, self.n)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.max
        if a <= l and r <= b:
            return self._lst[k]
        vl = self._query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self._query(a, b, k * 2 + 2, (l + r) // 2, r)
        return self.min(vl, vr)


def main():
    n, q = get_li()
    a = get_li()
    queries = []
    for _ in range(q):
        t, l, r = get_li()
        queries.append((t, l, r))

    b = list(enumerate(a))
    st = SegmentTree(b, _min=lambda x, y: x if x[1] < y[1] else y, _max=(inf, inf))
    for t, l, r in queries:
        if t == 1:
            vl = (r-1, st.lst[l-1][1])
            vr = (l-1, st.lst[r-1][1])
            st.update(l-1, vr)
            st.update(r-1, vl)
            st.update(l-1, vr)
        elif t == 2:
            i, _ = st.query(l-1, r)
            print(i+1)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


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