結果

問題 No.875 Range Mindex Query
ユーザー だれだれ
提出日時 2021-04-05 21:40:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 504 ms / 2,000 ms
コード長 3,715 bytes
コンパイル時間 393 ms
コンパイル使用メモリ 87,192 KB
実行使用メモリ 95,204 KB
最終ジャッジ日時 2023-08-30 08:19:26
合計ジャッジ時間 6,301 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
71,380 KB
testcase_01 AC 103 ms
76,292 KB
testcase_02 AC 139 ms
77,296 KB
testcase_03 AC 81 ms
75,680 KB
testcase_04 AC 88 ms
75,768 KB
testcase_05 AC 76 ms
71,148 KB
testcase_06 AC 103 ms
76,364 KB
testcase_07 AC 114 ms
77,024 KB
testcase_08 AC 88 ms
75,764 KB
testcase_09 AC 89 ms
76,512 KB
testcase_10 AC 118 ms
77,212 KB
testcase_11 AC 465 ms
91,404 KB
testcase_12 AC 412 ms
85,968 KB
testcase_13 AC 380 ms
94,908 KB
testcase_14 AC 387 ms
93,104 KB
testcase_15 AC 428 ms
95,144 KB
testcase_16 AC 473 ms
94,760 KB
testcase_17 AC 504 ms
94,728 KB
testcase_18 AC 486 ms
95,204 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