|
|
##[$AcWing$ $245$. 你能回答这些问题吗](https://www.acwing.com/problem/content/246/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
给定长度为 $N$ 的数列 $A$，以及 $M$ 条指令，每条指令可能是以下两种之一：
|
|
|
|
|
|
`1 x y`，查询区间 $[x,y]$ 中的 **最大连续子段和**，即 $\displaystyle \max_{x≤l≤r≤y}{\sum_{i=l}^rA[i]}$。
|
|
|
`2 x y`，把 $A[x]$ 改成 $y$。
|
|
|
|
|
|
对于每个查询指令，输出一个整数表示答案。
|
|
|
|
|
|
**输入格式**
|
|
|
第一行两个整数 $N,M$。
|
|
|
|
|
|
第二行 $N$ 个整数 $A[i]$。
|
|
|
|
|
|
接下来 $M$ 行每行 $3$ 个整数 $k,x,y，k=1$ 表示查询（此时如果 $x>y$，请交换 $x,y$），$k=2$ 表示修改。
|
|
|
|
|
|
**输出格式**
|
|
|
对于每个查询指令输出一个整数表示答案。
|
|
|
|
|
|
每个答案占一行。
|
|
|
|
|
|
**数据范围**
|
|
|
$N≤500000,M≤100000,
|
|
|
−1000≤A[i]≤1000$
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
5 3
|
|
|
1 2 -3 4 5
|
|
|
1 2 3
|
|
|
2 2 -1
|
|
|
1 3 2
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
2
|
|
|
-1
|
|
|
```
|
|
|
|
|
|
### 二、题目解析
|
|
|
|
|
|
本题依据题意需要进行 **单点修改**，因此无需懒标记+ $pushdown$ 操作，只需要 $pushup$ 操作即可。
|
|
|
|
|
|
对于查询区间内部的最大子段和，我们需要想想每个节点内部需要存储哪些信息才能保证儿子节点向父亲节点顺利`pushup`传递信息。（这是我们面对线段树题目时的一个很重要的思考点）
|
|
|
|
|
|
#### ① $l,r$
|
|
|
设线段树中的节点为$Node$(也就是一个线段树中节点对应的线段范围)，显然最先应该存储 **区间的左、右端点**：$l、r$，因为线段树本质上是一棵 **由区间作为节点的二叉树**。
|
|
|
|
|
|
#### ② $tmax$
|
|
|
同时，依据题意 **还应该存区间内部的最大连续子段和**，我们用`total_max`表示，简写为`tmax`。
|
|
|
|
|
|
#### ③ $lmax,rmax$
|
|
|
我们来想一下，只存这些信息就够了吗？只利用当前存储的信息，能够实现 **父节点的最大连续子段和**`tmax` 由 **两个儿子节点的最大连续子段和** 求出吗？
|
|
|
|
|
|
<font color='red' size=4><b>显然是不够的。</b></font>
|
|
|
|
|
|
**原因**：两个 **儿子节点** 各自`tmax`可能会出现完全处于区间内部的情况，且**不包含边界**，然而**父亲节点**的`tmax`可能会出现 **横跨两个区间** 的情况 。就好比下图所示（红色括号所包括的范围表示节点的`tmax`）：
|
|
|
<center><img src='https://img-blog.csdnimg.cn/img_convert/3af027a3dd3bf7c70b4739db45a15d45.png'></center>
|
|
|
|
|
|
对于像上图的这种 **父节点`tmax`横跨两个区间** 的这种情况，我们其实需要再 **额外存储两个信息**：
|
|
|
|
|
|
* ① **以左儿子区间右端点为起点 向左 的最大后缀和**
|
|
|
|
|
|
* ② **以右儿子区间左端点为起点 向右 的最大前缀和**
|
|
|
|
|
|
小结一下，也就是说每个节点还需要存储它的 **最大前缀和** 和 **最大后缀和**，这样， **父节点 横跨两区间 的最大连续子段和 = 左儿子的最大后缀和 + 右儿子的最大前缀和**。
|
|
|
|
|
|
（左右儿子区间完全独立，两者没有任何关系，没有限制，左右两区间取`max`即为父节点`tmax`）
|
|
|
|
|
|
我们设节点 **最大前缀和**为`lmax`，**最大后缀和** 为`rmax`。
|
|
|
|
|
|
我们有下面**三种情况**：
|
|
|
**父节点** `tmax` **没有横跨区间**的情况包含两种：
|
|
|
* ① 完全在左儿子区间内部：`tmax = 左儿子tmax`
|
|
|
* ② 完全在右儿子区间内部：`tmax = 右儿子tmax`
|
|
|
|
|
|
父节点`tmax` **横跨两区间** 情况为一种：
|
|
|
|
|
|
* ③`父节点u.tmax = 左儿子rmax + 右儿子lmax`
|
|
|
|
|
|
**综合一下得出表达式**：
|
|
|
|
|
|
$$父节点u.tmax = max(L_{son}.tmax, R_{son}.tmax, L_{son}.rmax + R_{son}.lmax)$$
|
|
|
|
|
|
至此，我们已有方法计算出每个节点内部的$tmax$了。
|
|
|
|
|
|
#### ④ $sum$
|
|
|
不过我们还需要想一下新加的两个变量：$lmax$（**最大前缀和**） 和 $rmax$（**最大后缀和**）如何得到。
|
|
|
|
|
|
和之前的思考方式类似，我们分情况来讨论：
|
|
|
|
|
|
对于一个父节点的$lmax$，我们也可以分为两种情况：
|
|
|
|
|
|
* ① 没有跨过分界点，如下图，$父节点lmax = 左儿子lmax$
|
|
|
|
|
|
<center><img src='https://img-blog.csdnimg.cn/img_convert/54e0e71d5a911e5070bd01e26705d950.png'></center>
|
|
|
|
|
|
* ② 跨过了分界点，如下图
|
|
|
|
|
|
<center><img src='https://img-blog.csdnimg.cn/img_convert/b3ab5ca894a2264a75a7174374fb7fef.png'></center>
|
|
|
|
|
|
对于上方的情况 ②，我们发现运用现有的条件是无法得到的:
|
|
|
|
|
|
**父节点最大前缀和$u.lmax$ = 左儿子$L_{son}.$区间总和 + 右儿子$R_{son}.lmax$**
|
|
|
|
|
|
同理:
|
|
|
|
|
|
**父节点最大后缀和$u.rmax$ = 右儿子$R_{son}.$区间总和 + 左儿子$L_{son}.rmax$**
|
|
|
|
|
|
所以说，我们的节点最后**还需要一个新的信息**：**区间和**（设为$sum$）
|
|
|
|
|
|
而对于 父节点$u.sum$也是可以计算出来的，我们可以由左儿子$L_{son}.sum$ + 右儿子$R_{son}.sum$
|
|
|
|
|
|
表达式：
|
|
|
$$父节点 u.sum = L_{son}.sum + R_{son.sum}$$
|
|
|
|
|
|
我们综合一下得出两个最大前后缀和的表达式：
|
|
|
|
|
|
**① 父节点$u.lmax = max(L_{son}.lmax, L_{son}.sum + R_{son}.lmax)$**
|
|
|
|
|
|
**② 父节点$u.rmax = max(R_{son}.rmax, R_{son}.sum + L_{son}.rmax)$**
|
|
|
|
|
|
至此，我们已经能够确定好存储线段树的结构体包含了哪些变量，进而可以确定$pushup$函数的编写，整个编码的大体框架不变，由四个函数构成：
|
|
|
<!-- 让表格居中显示的风格 -->
|
|
|
<style>
|
|
|
.center
|
|
|
{
|
|
|
width: auto;
|
|
|
display: table;
|
|
|
margin-left: auto;
|
|
|
margin-right: auto;
|
|
|
}
|
|
|
</style>
|
|
|
<div class="center">
|
|
|
|
|
|
| 序号 | 功能 | 函数名 |
|
|
|
| ---- | -------- | ---------------------------------- |
|
|
|
| ① | $build$ | 建立 |
|
|
|
| ② | $pushup$ | 将自己子孙后代的变化向上级领导汇报 |
|
|
|
| ③ | $modify$ | 修改 |
|
|
|
| ④ | $query$ | 查询 |
|
|
|
</div>
|
|
|
|
|
|
本题对于$query$函数另有分类等细节处理，详见代码。
|
|
|
|
|
|
#### 时间复杂度
|
|
|
$O(mlogn)（m<=1e5，n<=5e5）$
|
|
|
|
|
|
### 三、实现代码
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 500010;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
int n, m;
|
|
|
|
|
|
// 线段树
|
|
|
#define int long long
|
|
|
#define ls (u << 1)
|
|
|
#define rs (u << 1 | 1)
|
|
|
#define mid ((l + r) >> 1)
|
|
|
struct Node {
|
|
|
int l, r; // 区间范围
|
|
|
int sum; // 区间和
|
|
|
int lx; // 左后缀最大和
|
|
|
int rx; // 右前缀最大和
|
|
|
int mx; // 整体最大和
|
|
|
} tr[N << 2];
|
|
|
|
|
|
void pushup(int u) {
|
|
|
tr[u].sum = tr[ls].sum + tr[rs].sum; // 区间和
|
|
|
tr[u].lx = max(tr[ls].lx, tr[ls].sum + tr[rs].lx); // 左端区间和+右端前缀最大和
|
|
|
tr[u].rx = max(tr[rs].rx, tr[rs].sum + tr[ls].rx); // 右端区间和+左端后缀最大和
|
|
|
tr[u].mx = max({tr[ls].mx, tr[rs].mx, tr[ls].rx + tr[rs].lx}); // 三者取max
|
|
|
}
|
|
|
|
|
|
// 构建
|
|
|
void build(int u, int l, int r) {
|
|
|
tr[u].l = l, tr[u].r = r;
|
|
|
if (l == r) {
|
|
|
int x;
|
|
|
cin >> x;
|
|
|
tr[u].sum = tr[u].lx = tr[u].rx = tr[u].mx = x;
|
|
|
return;
|
|
|
}
|
|
|
build(ls, l, mid), build(rs, mid + 1, r);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
// 在以u节点为根的子树中，将位置x的值修改为v
|
|
|
void change(int u, int x, int v) {
|
|
|
int l = tr[u].l, r = tr[u].r;
|
|
|
if (l == r) { // 叶节点
|
|
|
tr[u].lx = tr[u].rx = tr[u].mx = tr[u].sum = v;
|
|
|
return;
|
|
|
}
|
|
|
if (x <= mid)
|
|
|
change(ls, x, v);
|
|
|
else
|
|
|
change(rs, x, v);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
// 查询
|
|
|
Node query(int u, int L, int R) {
|
|
|
int l = tr[u].l, r = tr[u].r;
|
|
|
if (l > R || r < L) return {0, 0, -INF, -INF, -INF, -INF}; // 如果查询区间与当前区间无交集，则返回空
|
|
|
if (l >= L && r <= R) return tr[u]; // 如果完整覆盖命中，则返回tr[u]
|
|
|
|
|
|
Node b;
|
|
|
Node lc = query(ls, L, R), rc = query(rs, L, R);
|
|
|
b.sum = lc.sum + rc.sum; // 区间和
|
|
|
b.lx = max(lc.lx, lc.sum + rc.lx); // 左端区间和+右端前缀最大和
|
|
|
b.rx = max(rc.rx, rc.sum + lc.rx); // 右端区间和+左端后缀最大和
|
|
|
b.mx = max({lc.mx, rc.mx, lc.rx + rc.lx}); // 三者取max
|
|
|
return b;
|
|
|
}
|
|
|
|
|
|
signed main() {
|
|
|
// 加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
|
|
|
cin >> n >> m;
|
|
|
|
|
|
build(1, 1, n);
|
|
|
|
|
|
int op, l, r;
|
|
|
while (m--) {
|
|
|
cin >> op >> l >> r;
|
|
|
if (op == 1) {
|
|
|
if (l > r) swap(l, r);
|
|
|
printf("%d\n", query(1, l, r).mx);
|
|
|
} else
|
|
|
change(1, l, r);
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
