Day 075-Q4 — Segment Tree Beats（区間 chmin + 区間加算 + 区間和）

問題

長さ $N$ の配列 $a$ に対して以下のクエリを $Q$ 回処理せよ。

• クエリ 1: $a[l], \ldots, a[r-1]$ のそれぞれを $\min(a[i], v)$ に更新（区間 chmin）
• クエリ 2: $a[l], \ldots, a[r-1]$ のそれぞれに $v$ を加算（区間加算）
• クエリ 3: $\sum_{i=l}^{r-1} a[i]$ を出力（区間和）

入出力例

5 5
3 1 4 1 5
1 0 5 3
3 0 5
2 1 3 2
1 0 5 4
3 0 5

12
16

概念図: Segment Tree Beats のノード情報

ヒント

def _apply_chmin(self, i, val):
    if val >= self.max1[i]: return
    # val > max2 が保証されている状態で呼ばれる
    self.sum_[i] -= (self.max1[i] - val) * self.cnt[i]
    self.max1[i] = val
    self.lazy_chmin[i] = min(self.lazy_chmin[i], val)

def update_chmin(self, l, r, val, i=1, lo=0, hi=None):
    if hi is None: hi = self.size
    if r <= lo or hi <= l or val >= self.max1[i]: return  # Break
    if l <= lo and hi <= r and val > self.max2[i]:
        self._apply_chmin(i, val); return  # Tag
    self._push_down(i)  # Continue: 子に再帰
    mid = (lo + hi) >> 1
    self.update_chmin(l, r, val, 2*i, lo, mid)
    self.update_chmin(l, r, val, 2*i+1, mid, hi)
    self._push_up(i)

模範解答

import sys
input = sys.stdin.readline
INF = float('inf')

class SegTreeBeats:
    def __init__(self, a):
        self.n = len(a); self.size = 1
        while self.size < self.n: self.size <<= 1
        N = 2 * self.size
        self.max1 = [-INF]*N; self.max2 = [-INF]*N
        self.cnt = [0]*N; self.sum_ = [0]*N
        self.sz = [0]*N
        self.lazy_add = [0]*N; self.lazy_chmin = [INF]*N
        for i in range(self.n):
            j = self.size + i
            self.max1[j] = a[i]; self.max2[j] = -INF
            self.cnt[j] = 1; self.sum_[j] = a[i]; self.sz[j] = 1
        for i in range(self.size - 1, 0, -1):
            self.sz[i] = self.sz[2*i] + self.sz[2*i+1]; self._push_up(i)

    def _push_up(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.cnt[i] = self.cnt[l]+self.cnt[r]
            self.max2[i] = max(self.max2[l], self.max2[r])
        elif self.max1[l] > self.max1[r]:
            self.max1[i] = self.max1[l]; self.cnt[i] = self.cnt[l]
            self.max2[i] = max(self.max2[l], self.max1[r])
        else:
            self.max1[i] = self.max1[r]; self.cnt[i] = self.cnt[r]
            self.max2[i] = max(self.max1[l], self.max2[r])

    def _apply_add(self, i, val):
        self.sum_[i] += val * self.sz[i]; self.max1[i] += val
        if self.max2[i] != -INF: self.max2[i] += val
        self.lazy_add[i] += val

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

    def _push_down(self, i):
        if self.lazy_add[i]:
            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_add(self, l, r, val, 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, val); return
        self._push_down(i); mid = (lo+hi)>>1
        self.update_add(l,r,val,2*i,lo,mid); self.update_add(l,r,val,2*i+1,mid,hi)
        self._push_up(i)

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

    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_down(i); mid = (lo+hi)>>1
        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):
        line = list(map(int, input().split()))
        if line[0] == 1: seg.update_chmin(line[1], line[2], line[3])
        elif line[0] == 2: seg.update_add(line[1], line[2], line[3])
        else: out.append(seg.query_sum(line[1], line[2]))
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

Step 1: Segment Tree Beats の鍵概念

通常の lazy SegTree は「操作が区間内の全要素に均一に適用できる」ときのみ有効。chmin は最大値のみを更新するため 不均一。Beats では「第2最大値 $M_2 < v \le M_1$（第1最大値）」のときのみ $M_1 \to v$ を 安全に 適用できる（$M_2$ 以下の要素は変化しない）。

Step 2: Break / Tag / Continue の3分岐

• Break: $v \ge M_1$ → 区間内の全要素 ≤ v なので何もしない
• Tag: $M_2 < v < M_1$ → 最大値の個数だけ $M_1 \to v$ に更新（sum は $(M_1 - v) \times \text{cnt}$ 減る）
• Continue: $v \le M_2$ → 最大値が複数種あるので子に再帰

Step 3: lazy_chmin と lazy_add の伝播順

_push_down では add を先に 子へ伝播し、その後 chmin を伝播する。順序が逆になると不正な結果になる（加算後に chmin が適用される必要があるため）。

Step 4: 計算量

各操作の amortized 計算量は $O(\log^2 N)$。Break が頻発するため Tag の総回数は $O((N+Q)\log N)$ に抑えられることが証明されている。

よくあるミス

次のステップ

• 発展問題: 区間 chmax（各要素を $\max(a[i], v)$ に更新）と区間 chmin を同時にサポートする拡張（Chtholly Tree との比較）

自己評価