結果

問題 No.1234 典型RMQ
コンテスト
ユーザー norioc
提出日時 2026-06-15 04:59:49
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 645 ms / 2,000 ms
コード長 2,434 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 364 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 96,896 KB
最終ジャッジ日時 2026-06-15 05:00:04
合計ジャッジ時間 14,341 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class RangeAddRangeMin:
    B = 512  # 一つのバケット幅

    def __init__(self, a: list):
        n = len(a)
        bsize = (n + self.B - 1) // self.B
        self.buckets = [0] * bsize
        self.add_buckets = [0] * bsize  # バケットへの加算
        self.min_buckets = [0] * bsize  # バケットの最小値
        self.data = a.copy()
        for i in range(bsize):
            start = i * self.B
            stop = min(n, (i+1) * self.B)
            self.min_buckets[i] = min([a[i] for i in range(start, stop)])

    def range_add(self, l: int, r: int, x: int):
        """[l, r) に x を加算"""
        assert 0 <= l < r <= len(self.data)
        for k in range(l // self.B, len(self.buckets)):
            nl = k * self.B
            nr = (k+1) * self.B
            if r <= nl: break
            if l <= nl and nr <= r:
                self.add_buckets[k] += x
                self.min_buckets[k] += x
            else:
                start = max(l, nl)
                stop = min(r, nr, len(self.data))
                for i in range(start, stop):
                    self.data[i] += x
                # バケットの最小値の更新
                self.min_buckets[k] = INF
                for i in range(nl, min(nr, len(self.data))):
                    s = self.add_buckets[k] + self.data[i]
                    self.min_buckets[k] = min(self.min_buckets[k], s)

    def range_min(self, l: int, r: int) -> int:
        """[l, r) の最小値"""
        assert 0 <= l < r <= len(self.data)
        res = INF
        for k in range(l // self.B, len(self.buckets)):
            nl = k * self.B
            nr = (k+1) * self.B
            if r <= nl: break
            if l <= nl and nr <= r:
                res = min(res, self.min_buckets[k])
            else:
                start = max(l, nl)
                stop = min(r, nr, len(self.data))
                for i in range(start, stop):
                    res = min(res, self.add_buckets[k] + self.data[i])

        return res


INF = 1 << 62
N = int(input())
A = list(map(int, input().split()))

sd = RangeAddRangeMin(A)
Q = int(input())
for _ in range(Q):
    qs = list(map(int, input().split()))
    match qs:
        case (1, L, R, C):
            L -= 1
            R -= 1
            sd.range_add(L, R+1, C)

        case (2, L, R, _):
            L -= 1
            R -= 1
            res = sd.range_min(L, R+1)
            print(res)
0