結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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