#3325. 「SNOI2020」区间和

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

有一个长度为 n 的整数数列 a_1, a_2, \dots, a_n (可能含有负数)。现在对其进行 q 次操作,每次操作是以下二者之一:

  • 0 l r x 表示对于 i = l, l+1, \dots, r ,将 a_i 赋值为 \max(a_i, x)
  • 1 l r 求区间 [l, r] 的最大子段和。即: \max(0, \max_{l\le u\le v\le r} (\sum_{i=u}^v a_i))

输入格式

第一行两个正整数 n,q ,分别表示序列长度和操作次数;

第二行 n 个正整数 a_1, a_2, \dots, a_n 表示初始的序列;

接下来 q 行,每行形如 0 l r x1 l r 表示一次操作。

输出格式

对于每个形如 1 l r 的操作,输出一行一个整数表示答案。

样例

样例输入

5 7
2 -4 6 -5 5
1 1 5
0 1 5 -4
1 1 5
0 3 4 -1
1 1 5
0 1 3 -1
1 1 5

样例输出

6
7
10
11

样例解释

  • 1 次询问时序列为 2,-4,6,-5,5 ,最大子段和为 6
  • 2 次询问时序列为 2,-4,6,-4,5 ,最大子段和为 6+(-4)+5=7
  • 3 次询问时序列为 2,-4,6,-1,5 ,最大子段和为 6+(-1)+5=10
  • 4 次询问时序列为 2,-1,6,-1,5 ,最大子段和为 2+(-1)+6+(-1)+5=11

数据范围与提示

对于所有数据, 1\le n\le10^5, 1\le q\le 2\times 10^5, |a_i|, |x|\le 10^9

  • 对于 10\% 的数据, n,q\le 200
  • 对于另外 10\% 的数据, n,q\le 2000
  • 对于另外 25\% 的数据,每次操作 0 均满足 l=r (即,只有单点修改);
  • 对于另外 20\% 的数据,每次操作 1 均满足 l = 1, r = n (即,只有全局询问);
  • 对于余下 35\% 的数据,无特殊限制。