#P5144. [Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?

    ID: 1593 传统题 2000ms 512MiB 尝试: 313 已通过: 19 难度: 10 上传者: 标签>难度分类省选/NOI-数据结构根号分块整块懒标记排序与序列处理最大子段和计算几何直线上包络单调栈凸多边形边向量归并离线与分治分治算法二分查找CF2900

[Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?

[Ynoi2018] 末日时在做什么?有没有空?可以来拯救吗?

题目描述

珂朵莉给了你一个长为 nn 的序列 aa,有 mm 次操作。

  1. 把区间 [l,r][l,r] 内所有数都加上 xx。
  2. 查询区间 [l,r][l,r] 内的最大子段和,可以不选数。

输入格式

从标准输入读入。第一行两个整数 n,mn,m。

第二行 nn 个整数表示序列 aa。

后面 mm 行:

  • 1 l r x:把区间 [l,r][l,r] 内所有数加上 xx。
  • 2 l r:查询区间 [l,r][l,r] 的最大子段和。

输出格式

对于每个询问,向标准输出写出一个数表示答案。

样例 #1

样例输入 #1

5 5
-2 -3 -3 -3 -3
2 1 5
1 2 4 4
2 1 5
1 2 3 1
2 3 3

样例输出 #1

0
3
2

样例 #2

样例输入 #2

5 5
-2 3 3 -3 3
2 1 5
1 2 4 -4
2 1 5
1 2 3 1
2 3 3

样例输出 #2

6
3
0

提示

1≤n,m≤1051 \le n , m \le 10^5,∣ai∣≤109| a_i | \leq 10^9,∣x∣≤109|x|\leq 10^9。

保证任意时刻 ∣ai∣≤2×109|a_i|\leq 2\times 10^9。