huanghai
/
python
1
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'main'
${ noResults }
python/TangDou/AcWing/SegmentTree/Gorgeous/P6242.md

309 lines
12 KiB
Raw Permalink Normal View History Unescape

'commit'
2 years ago
##[$P6242$ 【模板】线段树 (吉司机线段树) $3$](https://www.luogu.com.cn/problem/P6242)
未能AC掉，回头再看吧 2023.01.10
https://www.cnblogs.com/ZZM-248/p/16995016.html?share_token=64b71fe6-b62f-4adb-942a-7d135323116b
https://www.luogu.com.cn/blog/Sqrtree/solution-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)
[有趣的线段树维护——吉老师线段树学习笔记](https://www.watertomato.com/%e6%9c%89%e8%b6%a3%e7%9a%84%e7%ba%bf%e6%ae%b5%e6%a0%91%e7%bb%b4%e6%8a%a4-%e5%90%89%e8%80%81%e5%b8%88%e7%ba%bf%e6%ae%b5%e6%a0%91%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0/)
### 一、题目简介
给你一个长度为 $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})$。
### 二、思路
懒标记：
由来和定义：
众所周知，线段树可以支持O(logn)的时间复杂度的区间查询，但如果要进行区间修改的话会导致所有区间的在该区间内的节点的子树下的子节点的信息都要被修改，时间复杂度度为O(N).
如果之后却根本没有用到修改后的区间的信息则前面的修改操作都是浪费时间的，所以这里我们要给当前节点的区间都在修改区间内的节点都加上一个懒标记，并完成当前节点的修改，而至于该节点下的子树的修改则是留到下一次查询或者区间修改的时候将懒标记下传。
以区间增加的懒标记为例
前置知识：线段树。以及会写操作 $2$ 以外的所有操作。
[吉司机线段树模版题](https://blog.csdn.net/ZHUYINGYE_123456/article/details/126449970)，考虑用线段树维护。
先引入一下 $3$ 个概念：
- **$a_i$ 的历史最（小/大）值**：$a_{i}$ 存放过的最（小/大）的数
- **区间最（小/大）值操作**：将序列 $a$ 中区间 $[l,r]$ 中的数 $a_{i}$ 变为 $\min(a_i,x)$ 或 $\max(a_i,x)$,$i \in [l,r]$
- **严格次大值**：第二大的值，必须小于最大的
显然在这题中，
① $b_i$ 就是 $a_i$ 的 **历史最大值**
② 操作 $2$ 就是 **区间最小值操作**
③ 操作 $5$ 就是 **区间历史最大值**
本题我们可以发现，$B_i=max(B_i,A_i)$，因此$B$数组维护的是$A$数组的历史最大值，在线段树建树的时候，$A$数组和$B$数组就可以 **共用一颗线段树**
<!-- 让表格居中显示的风格 -->
<style>
.center
{
width: auto;
display: table;
margin-left: auto;
margin-right: auto;
}
</style>
<div class="center">
| **操作** | **描述** |
| ---- | ---- |
| 1 | 区间加 |
| 2 | 区间修改为最小值 |
| 3 | 询问区间和 |
| 4 | 查询区间最大值 |
| 5 | 查询区间历史最大值 |
</div>
#### 线段树结构体
- $l，r$：区间的左右端点
- $mx$：区间内的最大值
- $mxb$：区间内的历史最大值
- $cnt$：区间内最大值的个数
- $se$：区间内的严格次大值
- $sum$：区间内元素的和
- $add1$：$A$数组中 **最大值的懒标记**
- $add2$：$B$数组中 **最大值的懒标记**
- $add3$：$A$数组中 **除最大值外所有元素的懒标记**
- $add4$：$B$数组中 **除最大值外所有元素的懒标记**
```cpp {.line-numbers}
struct Node { // am为当前最大值，bm为历史最大值，se为严格次大值，cnt为区间内最大值的个数
int l, r, am, bm, cnt, se;
LL sum;
// add1为A[]中最大值加法加的最多的一次懒标记，add3为A[]中除最大值外所有元素加的最多的一次懒标记
// add2为B[]中最大值加法加的最多的一次懒标记，add4为B[]中除最大值外所有元素加的最多的一次懒标记
int add1, add2, add3, add4;
} tr[N << 2];
```
#### 建树
递归建树，当递归到了叶子节点时，初始化$sum，am，bm$都为$A$数组中的元素，$se$初始化为$INF$，这样能保证本题所有的数都比它大，$cnt$初始化为$1$，因为这个区间长度为$1$，只有一个最大值。
```cpp {.line-numbers}
void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r;
if (l == r) {
tr[u].sum = tr[u].am = tr[u].bm = read(); //初始化
tr[u].se = INF; //次大值初始化
tr[u].cnt = 1; //区间最大值的数量为1
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(u);
}
```
#### 向上更新
每次通过左右儿子来维护父节点的最大值和区间和
**父区间最大值出现的次数**：
- 当左右区间最大值相等时，父区间的最大值出现次数为两个子区间相加
- 否则，父区间最大值出现的次数为两个子区间中区间最大值大的那个区间的最大值出现次数
**父区间的严格次大值**：
- 当左右区间最大值相等时，父区间的次大值为两个子区间次大值大的那一个
- 否则，父区间次大值等于最大值小的那个区间的最大值和另一个区间的次大值取一个$max$
```cpp {.line-numbers}
void pushup(int u) {
tr[u].sum = tr[ls].sum + tr[rs].sum; //更新区间和
tr[u].am = max(tr[ls].am, tr[rs].am); //更新区间最大值
tr[u].bm = max(tr[ls].bm, tr[rs].bm); //更新区间历史最大值
//当左区间最大值与右区间最大值相等时
if (tr[ls].am == tr[rs].am) { //父区间次大值等于两个子区间次大值中大的一个
tr[u].se = max(tr[ls].se, tr[rs].se);
//父区间最大值个数等于两个子区间的和
tr[u].cnt = tr[ls].cnt + tr[rs].cnt;
} //左区间最大值大于右区间最大值
else if (tr[ls].am > tr[rs].am) { //父区间次大值等于max(左区间次大值，右区间最大值)
tr[u].se = max(tr[ls].se, tr[rs].am);
//父区间最大值个数等于左区间最大值个数
tr[u].cnt = tr[ls].cnt;
} //左区间最大值小于右区间最大值
else { //父区间次大值等于max(左区间最大值，右区间次大值)
tr[u].se = max(tr[ls].am, tr[rs].se);
//父区间最大值个数等于右区间最大值个数
tr[u].cnt = tr[rs].cnt;
}
}
```
#### 懒标记下放
为了方便理解，**将懒标记下放操作分为两个函数**，`update()`其实是`pushdown()`的子函数
<font color='red' size=4><b>$update()$函数</b></font>
**① 更新区间和**：把区间里的 **最大值个数** 乘上 $k1$，**其它数的个数** 乘上 $k3$，它们的和就是区间和新增的部分
**② 更新区间次大值**：如果区间不同值个数大于$1$，那么加上 $k3$
**③ 更新$4$个懒标记**
```cpp {.line-numbers}
/*
它爹手中有信息想要下传，它有信息包括：
*/
inline void update(int u, int k1, int k2, int k3, int k4) {
//区间和：把区间里最大值个数乘上add1，其他数的个数乘上add3，它们的和就是区间和新增部分
tr[u].sum += ((LL)k1 * tr[u].cnt) + ((LL)k3 * (tr[u].r - tr[u].l + 1 - tr[u].cnt));
tr[u].bm = max(tr[u].bm, tr[u].am + k2);
tr[u].am += k1;
//区间次大值：如果区间不同值个数不为一，那么加上add3
if (tr[u].se != INF) tr[u].se += k3;
//更新懒标记
tr[u].add2 = max(tr[u].add2, tr[u].add1 + k2);
tr[u].add4 = max(tr[u].add4, tr[u].add3 + k4);
tr[u].add1 += k1, tr[u].add3 += k3;
}
```
<font color='red' size=4><b>$pushdown()$函数</b></font>
对于每个子区间，如果它的最大值比另一区间的最大值大，那么父区间就要更新最大值，否则更新非最大值（注意，最大值需要先记录下来，不能在判断时比较两个子区间最大值大小）。
懒标记清零。
```cpp {.line-numbers}
inline void pushdown(int u) {
//对于左右子区间，如果其中一个区间的最大值比另一区间最大值大，那么父区间就要更新最大值，否则更新非最大值
int fmax = max(tr[ls].am, tr[rs].am);//取左右子树的最大值
if (tr[ls].am == fmax)//如果左子树中有最大值
update(ls, tr[u].add1, tr[u].add2, tr[u].add3, tr[u].add4);//更新最大值标签
else//如果左子树中没有最大值
update(ls, tr[u].add3, tr[u].add4, tr[u].add3, tr[u].add4);//更新非最大值标签
//复读机
if (tr[rs].am == fmax)
update(rs, tr[u].add1, tr[u].add2, tr[u].add3, tr[u].add4);
else
update(rs, tr[u].add3, tr[u].add4, tr[u].add3, tr[u].add4);
//更新后懒标记清零
tr[u].add1 = tr[u].add2 = tr[u].add3 = tr[u].add4 = 0;
}
```
#### 区间加
如果区间在待更新的范围内，那么把所有数都加上 `d` ，即 `update(u, d, d, d, d)`。
```cpp {.line-numbers}
void add(int u, int l, int r, int d) {
if (tr[u].l >= l && tr[u].r <= r) {
update(u, d, d, d, d);
return;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid) add(ls, l, r, d);
if (r > mid) add(rs, l, r, d);
pushup(u);
}
```
#### 区间修改为最小值
如果区间最大值都比 d 小，那么无需更新，直接 return。
否则，如果s e ≤ d ≤ a m se≤d≤amse≤d≤am，只需更新am，把update()中的k1和k2设置为d - tr[u].am（因为update()是加法操作，我们只需加上负数就等于减去这个数）。
```cpp {.line-numbers}
void change_min(int u, int l, int r, int d) {
if (tr[u].am <= d) return;
if (tr[u].l >= l && tr[u].r <= r && tr[u].se < d) {
update(u, d - tr[u].am, d - tr[u].am, 0, 0);
return;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid) change_min(ls, l, r, d);
if (r > mid) change_min(rs, l, r, d);
pushup(u);
}
```
#### 询问区间和
注意开long long
```cpp {.line-numbers}
LL querysum(int u, int l, int r) { //查询区间和
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
LL res = 0;
if (l <= mid) res = querysum(ls, l, r);
if (r > mid) res += querysum(rs, l, r);
return res;
}
```
#### 查询区间最大值
```cpp {.line-numbers}
int query_am(int u, int l, int r) { //查询max_a[i]
if (tr[u].l >= l && tr[u].r <= r) return tr[u].am;
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
int res = INF;
if (l <= mid) res = max(res, query_am(ls, l, r));
if (r > mid) res = max(res, query_am(rs, l, r));
return res;
}
```
#### 查询历史最大值
```cpp {.line-numbers}
int query_bm(int u, int l, int r) { //查询max_b[i]
if (tr[u].l >= l && tr[u].r <= r) return tr[u].bm;
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
int res = INF;
if (l <= mid) res = max(res, query_bm(ls, l, r));
if (r > mid) res = max(res, query_bm(rs, l, r));
return res;
}
```
https://blog.csdn.net/weixin_51053573/article/details/125821279