Day 014-Q1 — Segment Tree Beats

2026-04-27 赤色 Master / Phase 8+ ★★★★★★★★★ 区間 chmin + 加算 + sum

問題

長さ N の整数列 A に対し 4 種のクエリ: (1) 区間 chmin, (2) 区間加算, (3) 区間最大値, (4) 区間和。

制約

$1 \le N, Q \le 2 \times 10^5$
$0 \le A_i \le 10^9$
chmin: $0 \le v \le 10^9$
加算: $-10^9 \le x \le 10^9$

入出力例

入力例 1

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

出力例 1

12
7
22

ヒント (段階的開示)

ヒント1: 方向性
通常の遅延セグ木では区間 chmin + 区間和を $O(\log N)$ で扱えない。Segment Tree Beats（Ji Driver Segmentation）が必要。
ヒント2: アプローチ
各ノードで最大値 max1、2番目 max2、最大値の個数 cnt を管理。chmin(v) は max2 < v ≤ max1 なら lazy で完結、v ≤ max2 なら降りる。
ヒント3: 誘導
lazy_add と lazy_chmin の合成順序を「add → chmin」に統一。

模範解答 (Python)

import sys
from math import inf
input = sys.stdin.readline

class SegTreeBeats:
    def __init__(self, a):
        self.n = len(a)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.sum_ = [0] * (2 * self.size)
        self.max1 = [-inf] * (2 * self.size)
        self.max2 = [-inf] * (2 * self.size)
        self.cnt = [0] * (2 * self.size)
        self.lazy_add = [0] * (2 * self.size)
        self.lazy_chmin = [inf] * (2 * self.size)
        for i, v in enumerate(a):
            self.sum_[self.size + i] = v
            self.max1[self.size + i] = v
            self.max2[self.size + i] = -inf
            self.cnt[self.size + i] = 1
        for i in range(self.size - 1, 0, -1):
            self._pull(i)

    def _pull(self, i):
        l, r = 2*i, 2*i+1
        self.sum_[i] = self.sum_[l] + self.sum_[r]
        if self.max1[l] == self.max1[r]:
            self.max1[i] = self.max1[l]
            self.max2[i] = max(self.max2[l], self.max2[r])
            self.cnt[i] = self.cnt[l] + self.cnt[r]
        elif self.max1[l] > self.max1[r]:
            self.max1[i] = self.max1[l]
            self.max2[i] = max(self.max2[l], self.max1[r])
            self.cnt[i] = self.cnt[l]
        else:
            self.max1[i] = self.max1[r]
            self.max2[i] = max(self.max1[l], self.max2[r])
            self.cnt[i] = self.cnt[r]

    def _apply_add(self, i, x):
        self.sum_[i] += x * (self.size if i == 1 else 1)
        self.max1[i] += x
        if self.max2[i] != -inf:
            self.max2[i] += x
        self.lazy_add[i] += x
        if self.lazy_chmin[i] != inf:
            self.lazy_chmin[i] += x

    def _apply_chmin(self, i, v):
        if v >= self.max1[i]:
            return
        self.sum_[i] -= (self.max1[i] - v) * self.cnt[i]
        self.max1[i] = v
        self.lazy_chmin[i] = min(self.lazy_chmin[i], v)

    def _push(self, i):
        if self.lazy_add[i] != 0:
            self._apply_add(2*i, self.lazy_add[i])
            self._apply_add(2*i+1, self.lazy_add[i])
            self.lazy_add[i] = 0
        if self.lazy_chmin[i] != inf:
            self._apply_chmin(2*i, self.lazy_chmin[i])
            self._apply_chmin(2*i+1, self.lazy_chmin[i])
            self.lazy_chmin[i] = inf

    def update_chmin(self, l, r, v, i=1, lo=0, hi=None):
        if hi is None: hi = self.size
        if r <= lo or hi <= l or v >= self.max1[i]:
            return
        if l <= lo and hi <= r and v > self.max2[i]:
            self._apply_chmin(i, v)
            return
        self._push(i)
        mid = (lo + hi) // 2
        self.update_chmin(l, r, v, 2*i, lo, mid)
        self.update_chmin(l, r, v, 2*i+1, mid, hi)
        self._pull(i)

    def update_add(self, l, r, x, i=1, lo=0, hi=None):
        if hi is None: hi = self.size
        if r <= lo or hi <= l:
            return
        if l <= lo and hi <= r:
            self._apply_add(i, x)
            return
        self._push(i)
        mid = (lo + hi) // 2
        self.update_add(l, r, x, 2*i, lo, mid)
        self.update_add(l, r, x, 2*i+1, mid, hi)
        self._pull(i)

    def query_max(self, l, r, i=1, lo=0, hi=None):
        if hi is None: hi = self.size
        if r <= lo or hi <= l:
            return -inf
        if l <= lo and hi <= r:
            return self.max1[i]
        self._push(i)
        mid = (lo + hi) // 2
        return max(self.query_max(l, r, 2*i, lo, mid),
                   self.query_max(l, r, 2*i+1, mid, hi))

    def query_sum(self, l, r, i=1, lo=0, hi=None):
        if hi is None: hi = self.size
        if r <= lo or hi <= l:
            return 0
        if l <= lo and hi <= r:
            return self.sum_[i]
        self._push(i)
        mid = (lo + hi) // 2
        return (self.query_sum(l, r, 2*i, lo, mid) +
                self.query_sum(l, r, 2*i+1, mid, hi))

def solve():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    seg = SegTreeBeats(A)
    out = []
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 1:
            _, l, r, v = q
            seg.update_chmin(l-1, r, v)
        elif q[0] == 2:
            _, l, r, x = q
            seg.update_add(l-1, r, x)
        elif q[0] == 3:
            _, l, r = q
            out.append(seg.query_max(l-1, r))
        else:
            _, l, r = q
            out.append(seg.query_sum(l-1, r))
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

1通常の遅延では不可
chmin は最大値だけ変える非一様操作。単純な遅延では O(log N) 不可能。
2Break Condition
v ≥ max1: return／max2 < v < max1: lazy 適用／v ≤ max2: 子に降りる。これで全体 $O(N \log^2 N)$。
3加算と chmin の lazy 合成
add → chmin の順で統一。

よくあるミス

ミス原因正しい書き方
sum の更新漏れchmin 適用時に sum 更新せずsum -= (max1 - v) * cnt
lazy_chmin の初期値 -infchmin は上限なので不適inf
push 順序ミスchmin → add の順add → chmin で統一

次のステップ

  • chmax も同時サポートする完全版

自己評価

自分の回答

気づき・メモ