QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
统计

有一个长度为 $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\%$ 的数据,无特殊限制。