|
|
##[$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<k<maxn$ 的节点上更新。
|
|
|
|
|
|
具体的，我们在进行操作 $2$，正在线段树上递归时，会有以下 $3$ 种情况：
|
|
|
|
|
|
- $maxn≤v$：说明这个区间的最大值小于等于 $v$，直接返回即可
|
|
|
- $se<v<maxn$：说明这个区间的最大值会全部被修改成 $v$，但其它数和最大值的个数不变,修改后打上懒标记返回即可
|
|
|
- $v≤se$：无法更新，继续递归
|
|
|
|
|
|
思路大致就是在线段树中递归，直到该区间大于 $v$ 的数只有一种就更新。
|
|
|
|
|
|
总的时间复杂度: $O(mlog_2n)$
|
|
|
|
|
|
### 三、题解
|
|
|
首先说明，本题解主要以代码为主。个人认为代码写得很清晰，如果懂得上述思路就一定可以看懂。
|
|
|
|
|
|
先来看一下线段树每个节点需要存些什么。
|
|
|
|
|
|
- $add1$：区间最大值的懒标记
|
|
|
|
|
|
- $add2$：区间非最大值的懒标记
|
|
|
|
|
|
- $add3$：区间最大值的懒标记的最大值
|
|
|
|
|
|
- $add4$：区间非最大的值的懒标记的最大值
|
|
|
|
|
|
具体地，$add3$ 是在未下传懒标记前最大的 $add1$ 的值，$add4$ 是在未下传懒标记前最大的 $add2$ 的值。
|
|
|
|
|
|
这 $4$ 个 $tag$ 只要理解透了，代码就一定可以看得懂。
|
|
|
|
|
|
TODO
|
|
|
https://www.luogu.com.cn/blog/Sqrtree/solution-p6242 |
