4.1 KiB
一、题目简介
给你一个长度为 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 以外的所有操作。
吉司机线段树模版题，考虑用线段树维护。
先引入一下 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 只要理解透了，代码就一定可以看得懂。