截取峰值

废墟的尽头，是一座信号塔——不是普通的塔，是由无数频段叠加而成的共振柱。Echo说这座塔在发射一种持续的脉冲波，每一段脉冲的强度都不同。

"要截取最强的一段连续脉冲。"Echo说，"不是单个峰值——是连续的一段，总和最大。"

"就像……"CC想了想，"在一段杂音里找最响的连续哼唱？"

"对。"你说，"从左到右听，累加当前的音量。如果累加变成了负数，说明前面的都是噪音，重新开张。"

"但如果要查询任意一段区间的最强连续脉冲呢？"Echo问，"不是从头开始，是从中间某一段开始。"

"那就分段记账。"你说，"把整个频段切成很多小段，每段记录四个数：这段的最大连续脉冲、从左边开始的最大连续脉冲、从右边开始的最大连续脉冲、以及整段的总和。查询的时候，把覆盖那几段的账目合并起来。"

你开始写。建一本分层台账，每个节点存四个数。合并两个子节点时，最大连续脉冲要么在左子节点里，要么在右子节点里，要么是左子节点的右边界加上右子节点的左边界。

屏幕上跳出了结果。第47号段到第52号段的连续脉冲最强——那里是Zero的核心信号源。

"47号。"CC说，"又是47。"

"核心信号源。"Echo说，"Zero把最强的心跳放在那里。"

"那我们去掐断它？"

"不。"Echo说，"我们去监听它。"

题目描述

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

输入格式

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

输出格式

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

输入样例

4 2
1 2 -3 4
Q 1 4
U 3 3
Q 1 4

输出样例

0

提示

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

实时监控

八颗监控水晶，八本台账，全部厘清。

Echo站在G-30矿区的最深处，投影比以往任何时候都更明亮。她身后是一扇由能量束编织成的门，门上刻着一行字："数据结构的实战，才刚刚开始。"

"下一章。"她说，"是数据结构实战。"

"又是实战？"CC问。

"对。"Echo说，"这次是真正的大场面——预订舱位、描绘画卷、吟咏残章、统计流水。四道关卡，每道都需要把前面学的所有工具组合起来。"

[下一章：数据结构实战 —— G-30核心区]