##[$P6242$ 【模板】线段树 (吉司机线段树) $3$](https://www.luogu.com.cn/problem/P6242) [吉老师$PPT$下载](https://pan.baidu.com/s/1_QkSm2C0N-sqAqiBdpPkGg?pwd=36th) [参考题解I](https://www.luogu.com.cn/blog/Sqrtree/solution-p6242) [参考题解II](https://blog.csdn.net/Miniqwq/article/details/119618123) [参考题解III](https://www.luogu.com.cn/blog/Hakurei-Reimu/seg-beats) [视频资源](https://www.bilibili.com/video/BV1E7411A7D7) [$HDU$ $5306$ $Gorgeous$ $Sequence$](http://acm.hdu.edu.cn/showproblem.php?pid=5306) ### 一、题目简介 给你一个长度为 $n$ 的序列 $a$。令序列 $b=a$。 现在让你进行 $m$ 次操作，分为 $5$ 种： `1 l r k`：将序列 $a$ 中区间 $[l,r]$ 的数加上 $k$ `2 l r v`：将序列 $a$ 中区间 $[l,r]$ 的数对 $v$ 取最小值 `3 l r`：求序列 $a$ 中区间 $[l,r]$ 的数的和 `4 l r`：求序列 $a$ 中区间 $[l,r]$ 的数的最大值 `5 l r`：求序列 $b$ 中区间 $[l,r]$ 的数的最大值 每次操作后令 $b_{i}=\max(b_{i},a_{i})$。 ### 二、思路 前置知识：线段树。以及会写操作 $2$ 以外的所有操作。 [吉司机线段树模版题](https://blog.csdn.net/ZHUYINGYE_123456/article/details/126449970)，考虑用线段树维护。 先引入一下 $3$ 个概念： - **$a_i$ 的历史最（小/大）值**：$a_{i}$ 存放过的最（小/大）的数 - **区间最（小/大）值操作**：将序列 $a$ 中区间 $[l,r]$ 中的数 $a_{i}$ 变为 $\min(a_i,v)$ 或 $\max(a_i,v)$,$i \in [l,r]$ - **严格次大值**：最大的比最大值小的值，可以理解为最大值的前驱 显然在这题中， ① $b_i$ 就是 $a_i$ 的 **历史最大值** ② 操作 $2$ 就是区间最小值操作 ③ 操作 $5$ 是求区间最大历史最大值 接下来进入正题。 容易发现这道题的瓶颈在于进行操作 $2$ 后，**无法快速更新信息**。只能递归到叶子节点，然后对其取最小值。 这样写单次修改的时间复杂度就会达到惊人的 $O(n)$ 那怎么办呢？线段树显然不能直接区间取 $\min$。 换一个思路 : **把区间内大于 $v$ 的数都减去一个数，使得这些数都变为 $v$**。 因为不同的数要减去不同的数才能等于 $v$，显然我们不能设很多 $tag$ 来表示区间内不同的数要减去的数。 那退一步来讲，若区间内大于 $v$ 的数只有一种，我们可以怎么做呢？ 只需要维护一个 $tag$ 就行了。 那怎样才能使得区间内大于 $v$ 的数只有一种呢？ **只需要多递归几次就行了。**(啥意思？) 我们在线段树每个节点设以下 $3$ 个变量，分别为： - $maxn$：区间最大值 - $se$：区间严格次大值 - $cnt$：区间最大值个数 在区间只有一种数大于 $k$ 的时候,才能快速更新，即只能在满足 $se