吉司机线段树(Segment Beats)

What · 是什么

Segment Beats 是一种维护区间最值操作(区间 chmin/chmax)的懒标记线段树：每个节点记录最大值 mx1、严格次大值 mx2、最大值个数 cntm，当新值 x 满足 mx2<x<mx1 时可直接打标记(O(1))，否则暴力递归下传。用势能分析保证总复杂度 O(m log n)。

Why · 为什么

How · 实现

伪代码

apply_tag(p,x): 若 mx1[p]>x: sum+=cntm*(x-mx1); mx1=x
chmin(l,r,x,s,t,p): 若 mx1≤x 返回; 若 ⊆且 mx2<x: apply_tag; 否则 pushdown 递归 pull

Python 实现

import sys

# 区间 chmin(a_i, x) + 区间 max/sum 查询 (Segment Tree Beats)
INF = 1 << 60
mx1 = []   # 最大值
mx2 = []   # 严格次大值
cntm = []  # 最大值个数
sm = []    # 区间和


def build(a, s, t, p):
    if s == t:
        mx1[p] = a[s]; mx2[p] = -INF; cntm[p] = 1; sm[p] = a[s]
        return
    m = s + ((t - s) >> 1)
    build(a, s, m, p * 2); build(a, m + 1, t, p * 2 + 1)
    pull(p)


def pull(p):
    l, r = p * 2, p * 2 + 1
    sm[p] = sm[l] + sm[r]
    if mx1[l] > mx1[r]:
        mx1[p] = mx1[l]; cntm[p] = cntm[l]
        mx2[p] = max(mx2[l], mx1[r])
    elif mx1[l] < mx1[r]:
        mx1[p] = mx1[r]; cntm[p] = cntm[r]
        mx2[p] = max(mx1[l], mx2[r])
    else:
        mx1[p] = mx1[l]; cntm[p] = cntm[l] + cntm[r]
        mx2[p] = max(mx2[l], mx2[r])


def apply_tag(p, x):
    # chmin: 把当前最大值 mx1 限制为 x (仅当 mx1 > x)
    if mx1[p] <= x:
        return
    sm[p] += (x - mx1[p]) * cntm[p]
    mx1[p] = x


def pushdown(p):
    if mx1[p * 2] > mx1[p]:
        apply_tag(p * 2, mx1[p])
    if mx1[p * 2 + 1] > mx1[p]:
        apply_tag(p * 2 + 1, mx1[p])


def chmin(l, r, x, s, t, p):
    # 把 [l,r] 中 > x 的数变为 x
    if r < s or t < l or mx1[p] <= x:
        return
    if l <= s and t <= r and mx2[p] < x:
        apply_tag(p, x)
        return
    m = s + ((t - s) >> 1)
    pushdown(p)
    chmin(l, r, x, s, m, p * 2)
    chmin(l, r, x, m + 1, t, p * 2 + 1)
    pull(p)


def qmax(l, r, s, t, p):
    if l <= s and t <= r:
        return mx1[p]
    m = s + ((t - s) >> 1); pushdown(p); res = -INF
    if l <= m:
        res = max(res, qmax(l, r, s, m, p * 2))
    if r > m:
        res = max(res, qmax(l, r, m + 1, t, p * 2 + 1))
    return res


if __name__ == "__main__":
    sys.setrecursionlimit(1 << 20)
    n = 5
    a = [0, 10, 11, 12, 13, 14]
    k = 4 * n + 4
    for v in (mx1, mx2, cntm, sm):
        v.extend([0] * k)
    build(a, 1, n, 1)
    chmin(1, 5, 12, 1, n, 1)  # 所有>12的变12
    print(qmax(1, 5, 1, n, 1))  # 12

易错点

• mx2 必须是严格次大值(等于 mx1 的不算)，否则 chmin 标记会误伤
• 多种标记(加+chmin+chmax)并存时 apply/pushdown 顺序极易错，需逐种分析偏序关系
• 忘记在叶子节点特判导致 mx2 仍为 -INF 参与比较出错

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/ds/seg-beats.md
• web✓ https://atcoder.jp/contests/abc430/editorial/14433
• web△ https://codeforces.com/blog/entry/57319