#P7324. [2018年12月西安集训]核糖
[2018年12月西安集训]核糖
题目描述
有 颗核糖排成一列,第 颗的美味度为 ,可以为负数。
- 加工:选定区间 ,将其中每颗核糖的美味度都加上 。 可以为负数。
- 询问:给定区间 ,在其中选一个位置 ,取出从第 颗到第 颗的核糖作为礼物。求礼物美味度之和的最大值。
输入格式
第一行一个整数 。第二行 个整数 。第三行一个整数 ,表示操作数。
接下来 行,每行是以下一种操作:
- 0 L R k:将 中的每个 增加 。
- 1 L R:求 。
输出格式
每次询问输出一行一个整数。保证答案在 64 位有符号整数范围内。
样例
5
1 8 -3 3 -7
3
1 1 5
0 1 3 6
1 2 4
9
22
数据范围
样例中第二次询问时,选择 ,礼物的美味度为 。
- 对于 的数据,。
- 对于另外 的数据,所有修改操作满足 。
- 对于另外 的数据,所有询问操作满足 。
- 对于另外 的数据,修改操作不超过 个,所有询问满足 、。
- 原 PDF 对全部数据给出的上限是 。本评测站原有补充说明为 ,以及 (原说明未定义 )。