吉司机线段树

参考资料

• 吉司机线段树 - OI Wiki

简介

吉司机线段树（Segment Tree Beats）支持区间取 $\min$ / 取 $\max$ 等「非简单」区间操作。每个节点维护区间最大值、严格次大值与最大值的个数：区间对 $v$ 取 $\min$ 时，若 $v$ 落在次大值与最大值之间，只需更新最大值这一档，否则递归处理。均摊复杂度为 $O(n\log^2 n)$。

例题

洛谷 P6242 【模板】线段树 3（区间最值操作、区间历史最值）

维护一个序列，支持区间加、区间对 $v$ 取 $\min$、区间求和、区间最大值、区间历史最大值五种操作。