結果

問題 No.875 Range Mindex Query
ユーザー shirasu_oisishirasu_oisi
提出日時 2020-03-11 18:08:11
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,929 bytes
コンパイル時間 73 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 21,456 KB
最終ジャッジ日時 2024-04-27 19:22:16
合計ジャッジ時間 12,963 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 25 ms
10,752 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 WA -
testcase_17 WA -
testcase_18 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

INF = 10**6
class SegTree:
    def __init__(self, N, A, f, e):
        """
        N: A の要素数
        A: セグ木に乗せたい配列
        f: 二項演算 (モノイドじゃなきゃだめ)
        e: f の単位元
        """
        n = 2**(N-1).bit_length() # セグ木の葉の数（N 以上の最小の2べき）
        c = [e] * (2*n)

        for i in range(N):
            c[i+n] = A[i] # 葉をA[i]の値にする
        
        for i in range(n-1, 0, -1):
            c[i] = f(c[i<<1|0], c[i<<1|1]) # 子を使ってボトムアップに値を更新していく
        
        self.n = n # セグ木の葉の数（N 以上の最小の2べき）
        self.c = c # セグ木の配列
        self.e = e
        self.f = f
    
    def update(self, k, x):
        k += self.n
        self.c[k] = x # 対応する葉に移動

        # 祖先をたどって更新していく
        while k > 1:
            k >>= 1
            self.c[k] = self.f(self.c[k<<1|0], self.c[k<<1|1])

    def query(self, l, r):
        res = self.e
        l += self.n; r += self.n # 対応する葉に移動

        while l < r: # 範囲がかぶらない間
            if l & 1: # 左端が右側にいるなら
                res = self.f(res, self.c[l]) # その値と res の積をとって
                l += 1 # 右に 1 動く

            if r & 1: # 右端が左側にいるなら
                r -= 1 # 左に 1 動いて (右端は閉なので)
                res = self.f(res, self.c[r]) # その値と res の積をとる

            l >>= 1; r >>= 1 # 親に移動
        
        return res

N, Q = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

st = SegTree(N, A, min, INF)

for i in range(Q):
    q, l, r = [int(i)-1 for i in input().split()]
    if q:
        print(st.query(l, r)+1)
    else:
        nl, nr = A[r], A[l]
        st.update(l, nl); st.update(r, nr)
0