結果

問題 No.875 Range Mindex Query
ユーザー shirasu_oisi
提出日時 2020-03-11 18:08:11
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,929 bytes
コンパイル時間 135 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 21,328 KB
最終ジャッジ日時 2024-11-16 00:20:44
合計ジャッジ時間 15,279 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 17 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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