维护疆域

矿道的尽头是一扇巨大的铁门，门上刻着Zero的疆域图——整个矿区被划分成很多段，每段有一个驻军数量。Echo说Zero会不断调兵遣将，某一段的驻军可能突然增加或减少。

"要实时知道任意一段的驻军总数。"Echo说，"如果一段一段地加，每次查询都要从头数到尾，太慢了。"

"刷卡记账。"你说，"每次调兵不是在单段上加加减减，而是在两端做标记——起点加，终点减。查询的时候，把前面的标记一路累加，就是当前段的实际驻军。"

"就像……"CC想了想，"借钱和还钱？"

"对。"你说，"你今天借了一百，明天还了五十，后天又借了两百。想知道某天的余额，不需要一笔笔翻账本，只需要把前几天的净变化加起来。"

你开始写。用一个分层计数器维护这些标记——每次在某段起点加、终点减，查询某段的驻军时，把从开头到该段的所有标记累加。累加的过程不需要逐个加，而是沿着分层名册往上爬几层。

屏幕上跳出了结果。第47号段的驻军突然从12变成了47。

"又是47。"CC说。

"第47号段。"Echo说，"那是Zero的核心防线。它在往那里增兵。"

"那我们还去不去？"

"去。"Echo说，"但得快。"

题目描述

$n$ 个数，支持区间加和单点查询（或区间加和区间查询）。

输入格式

$n, m$。然后 $n$ 个数。然后 $m$ 个操作，每个操作是区间加或查询。

输出格式

每个查询输出结果。

输入样例

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

输出样例

13
13

提示

• 差分思想：区间加等价于在两端做标记。
• 用树状数组维护差分数组，支持单点查询和区间修改。
• 或线段树维护区间和，支持区间加和区间查询。

穿过铁门，是一片由发光石柱组成的广场。石柱排列成一排，高低不一，像是一群沉默的哨兵。Echo说这些石柱是Zero的"图腾"——每根石柱代表一个历史时刻的能量峰值。

"要解读图腾。"Echo飘到第一根石柱前，"找出有多少对石柱可以互相看见——中间没有更高的石柱挡住。"

"咋个找？"CC问，"一个个看？"

"从右往左看。"你说，"每根石柱往右看，能被它看见的石柱必须比它矮，而且中间不能有更高的。这像站岗——矮的站在高的前面，高的挡住后面所有的。"