結果

問題 No.875 Range Mindex Query
ユーザー だれだれ
提出日時 2021-04-05 21:40:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 473 ms / 2,000 ms
コード長 3,715 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 93,788 KB
最終ジャッジ日時 2025-01-01 17:01:55
合計ジャッジ時間 6,705 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
53,576 KB
testcase_01 AC 71 ms
72,148 KB
testcase_02 AC 100 ms
76,516 KB
testcase_03 AC 46 ms
61,284 KB
testcase_04 AC 55 ms
64,060 KB
testcase_05 AC 41 ms
55,912 KB
testcase_06 AC 71 ms
71,908 KB
testcase_07 AC 86 ms
75,916 KB
testcase_08 AC 55 ms
64,560 KB
testcase_09 AC 60 ms
67,268 KB
testcase_10 AC 93 ms
76,216 KB
testcase_11 AC 429 ms
90,452 KB
testcase_12 AC 394 ms
84,700 KB
testcase_13 AC 357 ms
93,788 KB
testcase_14 AC 368 ms
91,784 KB
testcase_15 AC 409 ms
93,536 KB
testcase_16 AC 449 ms
93,612 KB
testcase_17 AC 473 ms
93,608 KB
testcase_18 AC 450 ms
93,684 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