結果

問題 No.875 Range Mindex Query
ユーザー kurimupykurimupy
提出日時 2020-06-16 15:16:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,391 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 97,516 KB
最終ジャッジ日時 2024-07-03 11:51:58
合計ジャッジ時間 5,532 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
53,872 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 363 ms
95,076 KB
testcase_17 WA -
testcase_18 AC 379 ms
95,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# セグツリー(ぶっ壊れてる)
# 初期収納限界 2*10**5


class segTree():
    # 配列を保管する
    def __init__(self, N, function, basement):
        self.n = N
        self.K = 0
        self.func = function
        self.uint = basement
        while self.n > 2**self.K:
            self.K += 1
        # N<=2**Kが実現
        self.data = [self.uint for i in range(2**(self.K+1)-1)]

    def reset(self, basement, List):
        # 配列Listでbasementを新たに定義し、segtreeをリセットする
        for i in range(2**(self.K+1)-1):
            self.data[i] = basement
        Length = len(List)
        for _ in range(Length):
            self.data[2**self.K+-1+_] = List[_]
        for i in range(2**self.K-1, 0, -1):
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i])

    def find_min(self, p, q):
        if q <= p:
            return self.uint
        p += 2**self.K-1
        q += 2**self.K-2
        res = self.uint
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.data[p])
            if q & 1 == 1:
                res = self.func(res, self.data[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.data[p])
        else:
            res = self.func(self.func(res, self.data[p]), self.data[q])
        return res

    def update(self, index, value):
        # 配列において index 番目（0-index) の値をvalueに更新する
        now = 2**self.K-1+index
        self.data[now] = value
        while now:
            now = now >> 1
            self.data[now] = self.func(self.data[now*2+1], self.data[now*2+2])

    def change_in_func(self, function):
        self.func = function

# range mindex querie


def compare(X, Y):
    if X[0] < Y[0]:
        return X
    return Y


N, Q = map(int, input().split())
A = list(map(int, input().split()))
que = [tuple(map(int, input().split())) for _ in range(Q)]

for index, v in enumerate(A):
    A[index] = (v, index+1)

seg = segTree(N, compare, (N+1, -1))

seg.reset((N+1, -1), A)
for index, p, q in que:
    if index == 1:
        # swap
        v1 = seg.find_min(p-1, p)[0]
        v2 = seg.find_min(q-1, q)[0]
        seg.update(p-1, (v2, p))
        seg.update(q-1, (v1, q))
    else:
        mini = seg.find_min(p-1, q)[1]
        print(mini)
0