【笔记】吉如一线段树

吉如一论文（CQBZ内网，在 PDF 的 103 页

1 区间最值操作

1.1 区间取 min(max)，区间和

当前应该修改值为 \(x\);

维护区间最大值 \(mx\)，最大值个数 \(t\)，严格次大值 \(se\)。

如果走到一个区间上，如果：

1. \(x\ge mx\)，说明取min操作没用，直接 return；
2. \(mx>x>se\)，打标记，把 \(mx\) 改成 \(x\)，再用 \((mx-x)\times t\) 更新区间和；
3. 如果 \(x\le se\)，暴力走两边递归下去。

1.2 区间取 min/max，区间加，查询区间和

2 历史最值查询

3 历史和查询