#O1047. 区间加与区间最大值

区间加与区间最大值

题目描述

给定长度为 nn 的序列 aa,执行 qq 次操作:

  • 1 l r x:把 [l,r][l,r] 内所有数加上 xx;
  • 2 l r:询问 max⁡l≤i≤rai\max\limits_{l \le i \le r} a_i。

题目类型

线段树、懒标记

输入格式

第一行两个整数 n,qn, q。

第二行 nn 个整数。

接下来 qq 行,每行形如 1 l r x 或 2 l r。

输出格式

对每个 2 l r 操作输出一行一个整数。

样例 #1

样例输入 #1

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

样例输出 #1

5
-2

数据规模与约定

数据范围 说明
1≤n,q≤2×1051 \le n, q \le 2 \times 10^5 长度与操作数
−109≤x≤106-10^9 \le x \le 10^6 增量
−103≤ai≤103-10^3 \le a_i \le 10^3 初值
  • 区间修改与区间查询,需带懒标记下传,答案用 long long。