結果

問題 No.875 Range Mindex Query
ユーザー neterukunneterukun
提出日時 2019-09-06 21:32:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 828 ms / 2,000 ms
コード長 1,568 bytes
コンパイル時間 412 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 95,320 KB
最終ジャッジ日時 2024-06-24 16:57:51
合計ジャッジ時間 7,356 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
51,968 KB
testcase_01 AC 79 ms
69,724 KB
testcase_02 AC 91 ms
74,088 KB
testcase_03 AC 56 ms
60,288 KB
testcase_04 AC 65 ms
64,512 KB
testcase_05 AC 56 ms
61,952 KB
testcase_06 AC 75 ms
68,608 KB
testcase_07 AC 80 ms
69,632 KB
testcase_08 AC 65 ms
64,768 KB
testcase_09 AC 65 ms
64,888 KB
testcase_10 AC 91 ms
74,140 KB
testcase_11 AC 740 ms
91,400 KB
testcase_12 AC 671 ms
87,040 KB
testcase_13 AC 649 ms
95,212 KB
testcase_14 AC 644 ms
93,728 KB
testcase_15 AC 828 ms
95,240 KB
testcase_16 AC 540 ms
95,168 KB
testcase_17 AC 571 ms
95,064 KB
testcase_18 AC 610 ms
95,320 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: i番目をvalに変更する
    get_min: 区間[begin, end)の最小値を求める
    """
    def __init__(self, n):
        self.n = n
        self.INF = 2**31 - 1
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = min(self.node[2*i + 1], self.node[2*i + 2])

    def get_min(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = self.INF
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = min(s, self.node[end])
            if (begin - 1) & 1:
                s = min(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s

n, q = map(int, input().split())
a = list(map(int, input().split()))
st = SegmentTree(n)
for i in range(n):
    st.update(i, a[i])

pos = {}
for i in range(n):
    pos[a[i]] = i

for _ in range(q):
    j, l, r = map(int, input().split())
    if j == 1:
        tmp1 = st.get_min(l-1, l)
        tmp2 = st.get_min(r-1, r)
        st.update(r-1, tmp1)
        st.update(l-1, tmp2)
        pos[tmp1] = r-1
        pos[tmp2] = l-1
    if j == 2:
        print(pos[st.get_min(l-1, r)] + 1)
0