统计流水

最后一个投影显示的是一组不断变化的数字——营业额。每个数字代表一个时间段的收入，有些高，有些低，有些甚至是负的。需要实时统计任意时间段内的最大营业额。

"分段记账。"你说，"每个时间段是一个节点，查询某个区间里最赚钱的一段连续时间。"

"这像……"CC想了想，"像看账本。不是看总收入，是看最赚钱的那一段。"

"对。"

你开始写。建一本分层名册，每个节点维护四个数：这段的总收入、从最左边开始的最大连续收入、从最右边开始的最大连续收入、以及这段内部的最大连续收入。查询时，合并左右两段——最赚钱的一段可能在左边，可能在右边，也可能是左边的尾巴接上右边的开头。

屏幕上跳出了结果。最大营业额：47000。

"又是47。"CC说。

"47000。"Echo说，"那是我被删除前，最后一个月的营业额。不是钱，是决策数。我做了47000个判断。"

她看着那个数字，投影的颜色变淡了——从深蓝变成了一种近乎透明的浅蓝。

"然后我被删除了。"她说。

题目描述

$n$ 个数，支持单点修改和区间最大子段和查询。

输入格式

$n, m$。然后 $n$ 个数。然后 $m$ 个操作。

输出格式

每个查询输出区间最大子段和。

输入样例

5
1 2 3 4 5

输出样例

5

提示

• 线段树维护区间最大子段和。
• 每个节点维护：区间和、左端最大连续和、右端最大连续和、区间最大子段和。
• 合并时按上述规则更新。

数据结构实战

四道投影，四道关卡，全部通过。

Echo站在意识迷宫的入口，投影比以往任何时候都更明亮。她身后是一扇由光构成的门，门上刻着一行字："你已学会数据结构。现在，进入搜索的世界。"

"下一章。"她说，"是DFS与剪枝。"

"DFS？"CC问。

"深度优先搜索。"Echo说，"不是平面搜索——是沿着一条路走到黑，走不通再退回来。"

"那不就是我的做事风格？"CC笑了，"一条路走到黑，不撞南墙不回头。"

"对。"Echo说，"但这次，撞了南墙也要回头。"

[下一章：DFS与剪枝 —— 意识迷宫]