P4513 小白逛公园 题解
sto_5k_orz
·
·
题解
谁告诉你这题不能写树状数组了。
首先，考虑树状数组的每一段 x 表示 [x-lowbit(x)+1,x] 的结果。
那么每一段都要维护：
$lmax$，左半边的区间最大子段和。
$rmax$，右半边的区间最大子段和
$ans$，区间最大子段和。
那么一次合并操作，合并两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$，要求 $l_1\le r_1+1=l_2\le r_2$。
$sum$ 即为两端区间和。
$lmax$：可以考虑选 $[l_1,r_1]$ 的 $lmax$，也可以选整段 $[l_1,r_1]$ 和 $[l_2,r_2]$ 的 $lmax$。
$rmax$：同理要么选 $[l_2,r_2]$ 的 $rmax$，也可以选整段 $[l_2,r_2]$ 和 $[l_1,r_1]$ 的 $rmax$，
$ans$：即为 $[l_1,r_1]$ 的 $ans$ 或 $[l_2,r_2]$ 的 $ans$，也可以是 $[l_1,r_1]$ 的 $rmax$ 与 $[l_2,r_2]$ 的 $lmax$ 拼接而成。
~~所以考虑线段树上进行合并区间操作。~~
令 $merge(a,b)$ 表示合并 $a,b$ 区间后的四个值。
令 $Max(x,y)$ 表示 $x$ 到 $y$ 的维护区间最大子段和的四个值，然后树状数组叫做 $tr$，$tr_x=Max(x-lowbit(x)+1,x)$。
考虑查询，查询时当 $y-lowbit(y)>x$ 时，之间用 $tr_y$ 更新。$Max(x,y)=merge(Max(x,y-lowbit(y)),tr_y)$。
否则，就开始单点的暴力查询，令 $w_x$ 为 $x$ 的单点值。
$$Max(l,r)=merge(Max(l,r-1),w_r)$$
这是因为需要访问单点值，所以这种方法只支持单点修改。
单点修改呢？
设修改 $x$ 变为 $k$。
其实就是先把 $w_x$ 设成 $k$，然后从 $x$ 开始，到 $x+lbt(x),x+lbt(x)+lbt(x+lbt(x))\cdots$ 都用 $\log$ 的复杂度暴力修改。
这样做复杂度 $O(n\log^2 n)$，虽然线段树可以 $O(n\log n)$，但是 BIT 常数小无伤大雅。而且这么写码量小。
而且树状数组只能区间修改区间查询可差分信息，区间最大子段和这种不可差分信息只能单点修改。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define I inline
const int N = 500010; int a[N], n, m;
struct S {
int sum, lmax, rmax, ans;
void add(int u) {sum = ans = lmax = rmax = a[u];}
} tr[N], A[N];
I S merge(S a, S b) {
S ret;
ret.sum = a.sum + b.sum;
ret.ans = max(max(a.ans, b.ans), a.rmax + b.lmax);
ret.lmax = max(a.lmax, a.sum + b.lmax);
ret.rmax = max(b.rmax, b.sum + a.rmax);
return ret;
}
I int lbt(int x) {return x & (-x);}
I void change(int x, int k) {
A[x] = {k, k, k, k};
for(; x <= n; x += lbt(x)) {
tr[x] = A[x];
for(int i = 1; i < lbt(x); i <<= 1) {
tr[x] = merge(tr[x - i], tr[x]);
}
}
}
I int ask(int l, int r) {
if(l > r) swap(l, r);
S ret; ret.lmax = ret.rmax = ret.ans = -1e9; ret.sum = 0;
while(r >= l) {
ret = merge(A[r--], ret);
for(; r - lbt(r) >= l; r -= lbt(r)) ret = merge(tr[r], ret);
}
return ret.ans;
}
int main() {
cin >> n >> m; for(int i = 1, x; i <= n; i++) cin >> x, change(i, x);
while(m--) {
int o, x, y; cin >> o >> x >> y;
if(o == 2) change(x, y);
else cout << ask(x, y) << '\n';
}
return 0;
}
```
球赞 qwq。