打错了,N 是 5e5 + 9
by 5t0_0r2 @ 2023-08-30 16:24:37
@[5t0_0r2](/user/999274) getsum 的合并要和 pushup 一样,不能直接取 max,要将 getsum 返回值变成 node。
```cpp
return Node {
max(max(L.ms, R.ms), L.rms + R.lms),
L.s + R.s,
max(L.lms, L.s + R.lms),
max(R.rms, R.s + L.rms)
};
```
by Michaellg @ 2023-08-30 16:34:39
@[Michaellg](/user/670677) 能结合我的代码告诉我吗(好多变量我都没看懂什么意思)
by 5t0_0r2 @ 2023-08-30 16:38:34
@[5t0_0r2](/user/999274) ms,s,lms,rms 分别对应 val,sum,lsum,rsum
by Michaellg @ 2023-08-30 16:41:44
@[Michaellg](/user/670677) 那 L 和 R 呢?左右子节点?
by 5t0_0r2 @ 2023-08-30 16:44:29
@[5t0_0r2](/user/999274) 还要注意线段树 getsum 时如果子节点被递归了两次,复杂度会炸掉,所以要把子节点递归结果先记录下来
by Michaellg @ 2023-08-30 16:45:06
L 和 R 就是子节点的结果
by Michaellg @ 2023-08-30 16:45:44
@[Michaellg](/user/670677)
```cpp
node getsum(int l, int r, int now_l, int now_r, int root) {
int mid = (now_l + now_r) / 2,lchild = root * 2,rchild = root * 2 + 1;
if(in_range(l,r,now_l,now_r))
return tree[root];
else if(!out_range(l,r,now_l,now_r)){
push_down(now_l,now_r,root);
node L = getsum(l,r,now_l,mid,lchild),R = getsum(l,r,mid + 1,now_r,rchild);
return
(node){
L.sum + R.sum,
max(max(L.val,R.val),L.rsum + R.lsum),
max(L.lsum,L.sum + R.lsum),
max(R.rsum,R.sum + L.rsum),
tree[root].change
};
}
}
```
这样吗?现在爆零了
by 5t0_0r2 @ 2023-08-30 17:01:27
@[5t0_0r2](/user/999274) L.sum + R.sum 和 max(max(L.val,R.val),L.rsum + R.lsum 写反了
by Michaellg @ 2023-08-30 17:05:30
@[Michaellg](/user/670677) 还是爆零
by 5t0_0r2 @ 2023-08-30 17:09:10