区间最值操作 & 区间历史最值

本文讲解吉老师在 2016 年国家集训队论文 中提到的线段树处理历史区间最值的问题。

区间最值

笼统地说，区间最值操作指，将区间 $[l,r]$ 的数全部对 $x$ 取 $max$ 或 $min$，即 $a_i=max(a_i,x)$ 或者 $a_i=min(a_i,x)$。

HDU5306 Gorgeous Sequence

维护一个序列 $a$，执行以下操作：

1. 0 l r t $\mathrm{\forall }l\le i\le r,a_i=min(a_i,t)$。
2. 1 l r 输出 $\underset{i=l}{\overset{r}{max}}{a}_i$。
3. 2 l r 输出 $\sum _{i=l}^r{a}_i$。

多组测试数据，保证 $T\le 100,\sum n,\sum m\le {10}^6$。

区间取 $min$，意味着只对那些大于 $t$ 的数有更改。因此这个操作的对象不再是整个区间，而是「这个区间中大于 $t$ 的数」。于是我们可以有这样的思路：每个结点维护该区间的最大值 $Max$、次大值 $Se$、区间和 $Sum$ 以及最大值的个数 $Cnt$。接下来我们考虑区间对 $t$ 取 $min$ 的操作。

1. 如果 $Max\le t$，显然这个 $t$ 是没有意义的，直接返回；
2. 如果 $Se

---

本页面最近更新：2025/4/6 19:36:35，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, H-J-Granger, sshwy, countercurrent-time, Enter-tainer, NachtgeistW, CCXXXI, Ir1d, AngelKitty, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Konano, lanruixiang, LovelyBuggies, Makkiy, mgt, minghu6, opsiff, P-Y-Y, PotassiumWings, SamZhangQingChuan, Suyun514, weiyong1024, GavinZhengOI, Gesrua, GoatGirl98, hsfzLZH1, ImpleLee, kenlig, ksyx, kxccc, lychees, ouuan, Peanut-Tang, SukkaW, Tiphereth-A, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用