Day 059-Q2 — SegTree Walk + 遅延伝播

問題

長さ $N$ の数列 $A$ に対して $Q$ 個のクエリを処理せよ。

• 1 l r x: $A[l..r]$ の全要素に $x$ を加算する。
• 2 l r: $A[l..r]$ の中で、値が初めて $0$ 以下になる最左位置（1-indexed）を出力せよ。存在しなければ $-1$ を出力。

入出力例

6 4
3 5 -1 2 4 -3
2 1 6
1 2 3 -6
2 1 6
2 4 6

3
2
6

クエリ1: $A[1..6]$ で最左 $\le 0$ は位置3（$A_3=-1$）。
クエリ2: $A[2..3]$ に $-6$ 加算 → $A = [3,-1,-7,2,4,-3]$。
クエリ3: 最左 $\le 0$ は位置2（$A_2=-1$）。
クエリ4: $A[4..6] = [2,4,-3]$ → 最左 $\le 0$ は位置6。

概念図: SegTree Walk

ヒント（段階的開示）

def walk(node, node_l, node_r, ql, qr):
    if node_r < ql or qr < node_l or tree[node] > 0:
        return -1
    if node_l == node_r:
        return node_l + 1  # 1-indexed
    push_down(node)
    mid = (node_l + node_r) // 2
    res = walk(2*node, node_l, mid, ql, qr)
    if res != -1: return res
    return walk(2*node+1, mid+1, node_r, ql, qr)

模範解答 (Python)

コピーimport sys
from math import inf
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    SIZE = 1
    while SIZE < N: SIZE <<= 1

    tree = [inf] * (2 * SIZE)
    lazy = [0] * (2 * SIZE)

    for i in range(N):
        tree[SIZE + i] = A[i]
    for i in range(SIZE - 1, 0, -1):
        tree[i] = min(tree[2*i], tree[2*i+1])

    def push_down(node):
        if lazy[node]:
            for child in (2*node, 2*node+1):
                tree[child] += lazy[node]
                lazy[child] += lazy[node]
            lazy[node] = 0

    def update(node, node_l, node_r, ql, qr, val):
        if qr < node_l or node_r < ql: return
        if ql <= node_l and node_r <= qr:
            tree[node] += val
            lazy[node] += val
            return
        push_down(node)
        mid = (node_l + node_r) // 2
        update(2*node, node_l, mid, ql, qr, val)
        update(2*node+1, mid+1, node_r, ql, qr, val)
        tree[node] = min(tree[2*node], tree[2*node+1])

    def walk(node, node_l, node_r, ql, qr):
        if node_r < ql or qr < node_l or tree[node] > 0:
            return -1
        if node_l == node_r:
            return node_l + 1  # 1-indexed
        push_down(node)
        mid = (node_l + node_r) // 2
        res = walk(2*node, node_l, mid, ql, qr)
        if res != -1: return res
        return walk(2*node+1, mid+1, node_r, ql, qr)

    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 1:
            l, r, x = q[1]-1, q[2]-1, q[3]
            update(1, 0, SIZE-1, l, r, x)
        else:
            l, r = q[1]-1, q[2]-1
            print(walk(1, 0, SIZE-1, l, r))

main()

Step-by-Step 解説

Step 1: 遅延伝播セグメント木の設計

各ノードに区間最小値 tree[node] と遅延加算値 lazy[node] を持たせる。

Step 2: push_down の実装

内部ノードの遅延を子ノードに伝播: tree[child] += lazy[node]; lazy[child] += lazy[node]。その後 lazy[node] = 0。

Step 3: SegTree Walk の核心

「tree[node] > 0」（この部分木に $\le 0$ の要素なし）なら即座に $-1$ を返す。これにより探索が $O(\log N)$ に収まる。

Step 4: walk での push_down の必要性

子ノードへの分岐前に push_down が必須。遅延が伝播されていないと子の最小値が不正確になり正しい答えを返せない。

Step 5: 計算量

update: $O(\log N)$。walk: $O(\log N)$。全体 $O((N+Q)\log N)$。

よくあるミス

次のステップ

発展問題: 区間加算・区間最大値・最右 $\ge X$ 位置クエリを組み合わせた問題を実装せよ。

自己評価