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

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

区间最值

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

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

0 l r t $\forall l\le i\le r,~ a_i=\min(a_i,t)$。
1 l r 输出 $\max\limits_{i=l}^r a_i$。
2 l r 输出 $\sum\limits_{i=l}^r a_i$。

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

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

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

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用