結果

問題 No.1234 典型RMQ
ユーザー 👑 rin204rin204
提出日時 2022-01-27 09:40:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 818 ms / 2,000 ms
コード長 2,603 bytes
コンパイル時間 278 ms
コンパイル使用メモリ 87,148 KB
実行使用メモリ 96,268 KB
最終ジャッジ日時 2023-08-26 02:23:26
合計ジャッジ時間 21,719 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
71,196 KB
testcase_01 AC 70 ms
71,344 KB
testcase_02 AC 71 ms
71,344 KB
testcase_03 AC 70 ms
71,424 KB
testcase_04 AC 71 ms
71,324 KB
testcase_05 AC 71 ms
71,012 KB
testcase_06 AC 797 ms
91,108 KB
testcase_07 AC 735 ms
81,284 KB
testcase_08 AC 810 ms
96,020 KB
testcase_09 AC 777 ms
85,620 KB
testcase_10 AC 788 ms
94,036 KB
testcase_11 AC 775 ms
90,988 KB
testcase_12 AC 755 ms
84,604 KB
testcase_13 AC 710 ms
81,380 KB
testcase_14 AC 752 ms
85,004 KB
testcase_15 AC 767 ms
83,964 KB
testcase_16 AC 796 ms
93,728 KB
testcase_17 AC 768 ms
84,644 KB
testcase_18 AC 708 ms
80,696 KB
testcase_19 AC 818 ms
95,864 KB
testcase_20 AC 501 ms
94,976 KB
testcase_21 AC 804 ms
91,044 KB
testcase_22 AC 709 ms
96,268 KB
testcase_23 AC 706 ms
95,836 KB
testcase_24 AC 706 ms
96,264 KB
testcase_25 AC 719 ms
95,840 KB
testcase_26 AC 706 ms
95,848 KB
testcase_27 AC 71 ms
71,332 KB
testcase_28 AC 71 ms
71,348 KB
testcase_29 AC 69 ms
71,256 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LazySegTree_RAQ:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    add(l, r, x): 区間[l, r)にxを加算 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.lazy = [0] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
    def gindex(self, l, r):
        l += self.num
        r += self.num
        lm = l >> (l & -l).bit_length()
        rm = r >> (r & -r).bit_length()
        while r > l:
            if l <= lm:
                yield l
            if r <= rm:
                yield r
            r >>= 1
            l >>= 1
        while l:
            yield l
            l >>= 1
    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i]
            if v==0:
                continue
            self.lazy[i] = 0
            self.lazy[2 * i] += v
            self.lazy[2 * i + 1] += v
            self.tree[2 * i] += v
            self.tree[2 * i + 1] += v
    def add(self, l, r, x):
        *ids, = self.gindex(l, r)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] += x
                self.tree[l] += x
                l += 1
            if r & 1:
                self.lazy[r - 1] += x
                self.tree[r - 1] += x
            r >>= 1
            l >>= 1
        for i in ids:
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1]) + self.lazy[i]
    def query(self, l, r):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def segfunc(x, y):
    return min(x, y)

n = int(input())
A = list(map(int, input().split()))
inf = 1 << 60
seg = LazySegTree_RAQ(A, segfunc, inf)

q = int(input())
for _ in range(q):
    k, l, r, c = map(int, input().split())
    if k == 1:
        seg.add(l - 1, r, c)
    else:
        print(seg.query(l - 1, r))
0