結果

問題 No.1234 典型RMQ
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:22:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,406 ms / 2,000 ms
コード長 2,133 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 82,488 KB
実行使用メモリ 136,068 KB
最終ジャッジ日時 2025-03-20 20:25:07
合計ジャッジ時間 23,016 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class SegmentTreeNode:
    __slots__ = ['l', 'r', 'left_child', 'right_child', 'add', 'min_val']
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left_child = None
        self.right_child = None
        self.add = 0
        self.min_val = 0

def build(l, r, a):
    node = SegmentTreeNode(l, r)
    if l == r:
        node.min_val = a[l-1]
        return node
    mid = (l + r) // 2
    node.left_child = build(l, mid, a)
    node.right_child = build(mid + 1, r, a)
    node.min_val = min(node.left_child.min_val, node.right_child.min_val)
    return node

def push_down(node):
    if node.add != 0 and node.left_child is not None:
        left = node.left_child
        right = node.right_child
        left.add += node.add
        left.min_val += node.add
        right.add += node.add
        right.min_val += node.add
        node.add = 0

def update_range(node, l, r, delta):
    if node.r < l or node.l > r:
        return
    if l <= node.l and node.r <= r:
        node.add += delta
        node.min_val += delta
        return
    push_down(node)
    update_range(node.left_child, l, r, delta)
    update_range(node.right_child, l, r, delta)
    node.min_val = min(node.left_child.min_val, node.right_child.min_val)

def query_range(node, l, r):
    if node.r < l or node.l > r:
        return float('inf')
    if l <= node.l and node.r <= r:
        return node.min_val
    push_down(node)
    left_min = query_range(node.left_child, l, r)
    right_min = query_range(node.right_child, l, r)
    return min(left_min, right_min)

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    a = list(map(int, input[ptr:ptr+N]))
    ptr += N
    root = build(1, N, a)
    Q = int(input[ptr])
    ptr += 1
    for _ in range(Q):
        k = int(input[ptr])
        l = int(input[ptr+1])
        r = int(input[ptr+2])
        c = int(input[ptr+3])
        ptr += 4
        if k == 1:
            update_range(root, l, r, c)
        else:
            res = query_range(root, l, r)
            print(res)

if __name__ == '__main__':
    main()
0