結果

問題 No.875 Range Mindex Query
ユーザー だれだれ
提出日時 2021-04-05 21:40:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 457 ms / 2,000 ms
コード長 3,715 bytes
コンパイル時間 419 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 94,020 KB
最終ジャッジ日時 2024-06-10 08:47:00
合計ジャッジ時間 5,509 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,024 KB
testcase_01 AC 71 ms
71,040 KB
testcase_02 AC 100 ms
76,032 KB
testcase_03 AC 46 ms
60,800 KB
testcase_04 AC 57 ms
63,872 KB
testcase_05 AC 40 ms
54,784 KB
testcase_06 AC 74 ms
71,040 KB
testcase_07 AC 86 ms
75,880 KB
testcase_08 AC 55 ms
64,128 KB
testcase_09 AC 57 ms
65,664 KB
testcase_10 AC 90 ms
76,160 KB
testcase_11 AC 384 ms
90,448 KB
testcase_12 AC 334 ms
84,812 KB
testcase_13 AC 311 ms
93,748 KB
testcase_14 AC 322 ms
91,976 KB
testcase_15 AC 367 ms
93,684 KB
testcase_16 AC 431 ms
93,464 KB
testcase_17 AC 457 ms
93,568 KB
testcase_18 AC 446 ms
94,020 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
    def __init__(self, array, f = lambda x, y: x + y, inf = 0):
        self.f = f
        self.id = inf
        if isinstance(array, int):
            self.n = array
            self.tree = [self.id] * (self.n << 1)

        else:
            self.height = (len(array) - 1).bit_length()
            self.n = 1 << (self.height)
            self.tree = [self.id] * (self.n << 1)
            for i in range(len(array)):
                self.tree[self.n + i] = array[i]
            for i in range (self.n - 1, 0, -1):
                self.tree[i] = self.f (self.tree[i << 1], self.tree[i << 1 | 1])



    def get(self, i):
        return self.tree[i + self.n]


    def update(self, i, x):
        i += self.n
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.f (self.tree[i << 1], self.tree[i << 1 | 1])


    def query(self, l, r):
        l += self.n
        r += self.n
        lf, rf = self.id, self.id
        while l < r:
            if l & 1:
                lf = self.f (lf, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                rf = self.f (self.tree[r], rf)
            l >>= 1
            r >>= 1
        return self.f (lf, rf)


    def query_all(self):
        return self.tree[1]


    def display(self):
        for i in range(self.n, self.n << 1):
            print(self.tree[i], end=" ")
            while i % 2 == 0:
                i >>= 1
                print(self.tree[i], end=" ")
            print()


    def min_left(self, l, r, f, sss):
        nr = r
        lv, rv = [], []

        l += self.n
        r += self.n

        while l < r:
            if l & 1:
                lv.append(l)
                l += 1
            if r & 1:
                r -= 1
                rv.append(r)
            l >>= 1
            r >>= 1

        now = self.id
        for i in lv + rv[::-1]:
            if f(self.f(now, self.tree[i]), sss):
                while True:
                    if f(self.f(now, self.tree[i]), sss):
                        if i >= self.n:
                            return i - self.n + 1
                        i <<= 1
                    else:
                        now = self.f(now, self.tree[i])
                        i += 1
            else:
                now = self.f(now, self.tree[i])

        return nr + 1


    def max_right(self, l, r, f, sss):
        nl = l
        lv, rv = [], []

        l += self.n
        r += self.n

        while l < r:
            if l & 1:
                lv.append(l)
                l += 1
            if r & 1:
                r -= 1
                rv.append(r)
            l >>= 1
            r >>= 1

        now = self.id
        for i in rv + lv[::-1]:
            if f(self.f(self.tree[i], now), sss):
                while True:
                    if f(self.f(self.tree[i], now), sss):
                        if i >= self.n:
                            return i - self.n + 1
                        i <<= 1
                        i += 1
                    else:
                        now = self.f(self.tree[i], now)
                        i -= 1
            else:
                now = self.f(self.tree[i], now)

        return nl

n, q = map(int, input().split())
a = list(map(int, input().split()))

S = SegmentTree(a, min, 1e9)

ans = []

def search(a, b):
    return a <= b

for _ in range(q):
    t, l, r = map(int, input().split())
    if t == 1:
        l -= 1
        r -= 1
        x = S.get(l)
        y = S.get(r)
        S.update(l, y)
        S.update(r, x)
    else:
        l -= 1
        x = S.query(l, r)
        ans.append(S.min_left(l, r, search, x))

print(*ans, sep = "\n")
0