构筑篱笆

广场尽头出现了一座高架桥——不是普通的桥，是由能量束编织成的通道。Echo飘到桥头，投影被能量束的光芒切割成碎片。

"下一关。"她说，"是构筑篱笆。"

"篱笆？"CC问。

"对。"Echo说，"用能量束围成一圈篱笆，把G-30的核心区域围起来。篱笆的高度要够高，挡住所有外来的入侵者。"

"那不就是找最高的连续段？"你说。

"对。"Echo说，"但不是简单的高——是连续的高。如果中间有一段塌陷了，整个篱笆就断了。"

你开始写。把整个区域切成很多小段，每段的高度单独记录。查询某一段的最低高度时，不需要从头看到尾，只需要把覆盖那几段的账目合并起来——取最小值。修改某一段的高度时，从那一页往上翻，每一级重新算两个子节点的最小值。

"就像……"CC想了想，"查户口。每个街区有个最低收入，想知道几个街区连起来的最低收入，直接查汇总表。"

"对。"

屏幕上跳出了结果。第47号段到第52号段的高度最低——那里是篱笆的薄弱点。

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

"薄弱点。"Echo说，"Zero故意把最弱的地方放在最显眼的位置——就像诱捕器。"

"那我们绕过去？"

"不。"Echo说，"我们加固它。"

题目描述

$n$ 个数，支持区间修改（加或赋值）和区间最小值查询。

输入格式

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

输出格式

每个查询输出区间最小值。

输入样例

3 3
1 2 3
Q 1 3
C 2 5
Q 1 3

输出样例

6
6

提示

• 线段树维护区间最小值，支持懒标记。
• 修改时从叶子往上更新，查询时合并覆盖区间的节点值。

穿过高架桥，是一片废墟——不是被炸毁的，是被时间遗忘的。断壁残垣之间，散落着无数块能量地毯。每块地毯有一个矩形覆盖区，颜色各异。Echo说这些地毯是Zero曾经划分的势力范围，现在要丈量它们的总面积。

"不能一块一块量。"你说，"很多地毯重叠了，直接加会重复计算。"

"那咋个办？"CC问。

"铺卷尺。"你说，"从左走到右，每遇到一块地毯的左边界，就把它铺开的上下范围记下来；每遇到右边界，就把那片范围收起来。一路上，随时量当前铺开的地毯有多宽。"