結果

問題 No.1234 典型RMQ
ユーザー 👑 rin204rin204
提出日時 2022-01-27 09:40:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 812 ms / 2,000 ms
コード長 2,603 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 95,232 KB
最終ジャッジ日時 2024-06-06 21:17:56
合計ジャッジ時間 19,978 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,608 KB
testcase_01 AC 42 ms
52,480 KB
testcase_02 AC 42 ms
52,352 KB
testcase_03 AC 42 ms
52,736 KB
testcase_04 AC 42 ms
52,096 KB
testcase_05 AC 43 ms
52,352 KB
testcase_06 AC 791 ms
90,112 KB
testcase_07 AC 730 ms
79,440 KB
testcase_08 AC 804 ms
95,232 KB
testcase_09 AC 782 ms
84,004 KB
testcase_10 AC 794 ms
92,716 KB
testcase_11 AC 780 ms
89,604 KB
testcase_12 AC 773 ms
83,080 KB
testcase_13 AC 714 ms
80,100 KB
testcase_14 AC 743 ms
83,276 KB
testcase_15 AC 774 ms
82,560 KB
testcase_16 AC 802 ms
93,056 KB
testcase_17 AC 772 ms
83,480 KB
testcase_18 AC 695 ms
79,996 KB
testcase_19 AC 812 ms
94,976 KB
testcase_20 AC 490 ms
93,796 KB
testcase_21 AC 796 ms
89,856 KB
testcase_22 AC 699 ms
94,936 KB
testcase_23 AC 699 ms
95,056 KB
testcase_24 AC 694 ms
94,976 KB
testcase_25 AC 718 ms
95,104 KB
testcase_26 AC 692 ms
94,976 KB
testcase_27 AC 41 ms
52,352 KB
testcase_28 AC 42 ms
52,352 KB
testcase_29 AC 42 ms
52,352 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