[Ynoi2015]世上最幸福的女孩

题目描述

我有一个请求 最后的请求 我感觉自己好像跟他有过约定 说好了那个人以后不必再战斗 说好了那个人的战斗全部由我来继承 而且我还有话想对他说,所以拜托你了 ![](https://cdn.luogu.com.cn/upload/pic/45581.png) 【无论如何都要?】 嗯,无论如何都要 【但是,如果再来一次,珂朵莉就会彻底消失了哦?】 【不光是回忆,包括那所有珍贵的情感】 【全都会彻底消失的哦!?】 那还挺让人受不了的呢 但是呢,比起消失,我更加讨厌就这么结束啊 【珂朵莉...】 所以,拜托你了 让我再一次,回到那个地方吧 ![](https://cdn.luogu.com.cn/upload/pic/45582.png) “珂朵莉,加油” ![](https://cdn.luogu.com.cn/upload/pic/45583.png) ![](https://cdn.luogu.com.cn/upload/pic/45584.png) ![](https://cdn.luogu.com.cn/upload/pic/45585.png) 威廉… 谢谢你…

输入输出格式

输入格式


在最后的最后,珂朵莉给了你一个长为 $n$ 的序列,有 $m$ 个操作: 1. 全局加(即序列的所有数加)。 2. 查询区间最大子段和。

输出格式


第一行两个整数 $n,m$。 第二行 $n$ 个数表示这个序列。 之后 $m$ 行,每行一个操作。 * $1\ x$ : 所有数都加上 $x$。 * $2\ l\ r$ : 查询区间 $[l,r]$ 内的最大子段和(可以不选数,此时最大子段和是 $0$)。

输入输出样例

输入样例 #1

5 7
-10 -3 -2 -4 -5
2 2 4
1 5
2 2 4
1 3
2 1 5
1 2
2 3 5

输出样例 #1

0
6
18
19

说明

Idea:nzhtl1477,Solution:ccz181078,Code:nzhtl1477,Data:nzhtl1477 $1\leq n \leq 3\times 10^5$,$1 \leq m \leq 6\times 10^5$,序列中的数绝对值 $\leq 2\times 10^9$,$1$ 操作中的 $x$ 的绝对值 $\leq 5\times 10^7$。