#1682. 线段树经典题

线段树经典题

题目描述

这是一道线段树经典题。

你需要写一个数据结构(线段树)维护长度为 n n ​ 的三个序列 A,B,C A,B,C ​,下标为 1n 1\sim n ​,支持:

  • 对于 i[l,r] i\in[l,r] ,令 Aimin(Ai,x) A_i\leftarrow\min (A_i,x)

  • 对于 i[l,r] i\in [l,r] ,令 AiAi+x A_i\leftarrow A_i+x

  • i=lrAi \sum_{i=l}^r A_i ​

  • i=lrBi \sum_{i=l}^r B_i

  • maxi=lrCi \max_{i=l}^r C_i

每次修改操作后(前两种操作),令 $ B_i\leftarrow B_i+A_i,C_i\leftarrow\max(C_i,A_i) ​$。

初始给定 Ai A_i ,同时初始 Bi=0,Ci=Ai B_i=0,C_i=A_i

输入格式

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

第二行 n n 个整数表示序列 Ai A_i

接下来 Q Q 行,每行第一个整数表示操作类型编号,其他数字意义同题面:

  • 若为类型 1 1 ​,接下来三个整数 l,r,x l,r,x ​
  • 若为类型 2 2 ,接下来三个整数 l,r,x l,r,x
  • 若为类型 3 3 ​,接下来两个整数 l,r l,r ​
  • 若为类型 4 4 ,接下来两个整数 l,r l,r
  • 若为类型 5 5 ,接下来两个整数 l,r l,r

输出格式

对于每个类型为 3,4,5 3,4,5 ​ 的操作,输出一行一个整数表示答案。

样例 1

10 10
-3 -1 -1 2 -2 2 5 2 3 -3
2 2 6 2
4 5 8
5 6 9
1 6 7 -4
2 3 8 6
3 4 5
5 1 3
1 5 7 -7
4 5 9
5 2 8
11
5
16
7
22
10
10 10
3 -5 -2 -2 3 -1 -1 3 -4 -4
4 5 8
2 1 10 -5
3 1 7
1 8 9 -3
5 1 10
3 7 10
2 2 4 -4
4 1 2
5 8 8
1 2 8 1
0
-40
3
-27
-40
3

数据范围与提示

对于 100% 100\% 的数据,1n,Q2×105,ai109 1\leq n,Q\leq 2\times 10^5,|a_i|\leq 10^9 1lrn1\leq l\leq r\leq n,数据保证过程中所有相关数值及输出的绝对值均在 long long 范围内。

数据均为随机,但没有梯度。