#6bwj5e. 令人感伤的红雨

时间限制：2.5 s       空间限制：500 MiB       标签： 洛谷 洛谷公开赛 缺题解 

算法难度等级：0       思维难度等级：0       实现难度等级：0

题目背景

秋静叶是在秋季掌管落叶的神明。在秋季即将迎来落幕之时，因她的力量使然，山里会变得火红一片。同时，将红叶变为落叶也是她工作的一环。

秋穰子是在秋季掌管丰收的神明。与秋静叶的职责相反，她掌管着秋天果实的成熟、秋粮的收获。

交织着快乐与忧愁的秋天，怎能让人不有感而发呢？

题目描述

秋穰子和秋静叶是掌管秋天的神灵，因而控制着田地的收成。具体而言，有 $n$ 块田依次排列，第 $i$ 块田的丰收程度为 $a_i$。秋之姐妹会据此得出一年的年成。

在综合考察了各方面因素后，秋之姐妹得出了收获第 $l$ 块至第 $r$ 块田地可以获得的作物总量 $\Omega(l,r)$。具体定义如下：

$A(l,r)=\max_{i=l}^r \{i \times [a_i = \max_{j=l}^r \{a_j\}]\}$

$B(l,r) = \max_{i=l}^r \min_{j=1}^i A(j,i) - \min_{i=l}^r \max_{j=1}^i A(j,i)$

$\Omega(l,r) = \min_{i=l}^r \min_{j=i}^r |B(i,j)|$

在提示说明部分有相关符号的解释。

由于相关因素的影响，田地的丰收程度会发生变化。因此秋之姐妹会对 $a$ 进行 $q$ 次操作：

1. 形如 1 x y，表示让 $a_1,a_{2},a_{3},\cdots ,a_x$ 分别加上 $y$。
2. 形如 2 l r，表示询问 $\Omega(l,r)$ 的值。

输入格式

• 第一行有两个正整数 $n,q$，分别表示田地总数、操作次数。
• 接下来一行有 $n$ 个整数，表示每块田地的丰收程度。
• 接下来 $q$ 行，第一个数字 $op$ 表示该操作的种类。
  • 如果 $op=1$，那么接下来会有两个整数 $x,y$，含义如题意所示。
  • 如果 $op=2$，那么接下来会有两个正整数 $l,r$，含义如题意所示。

输出格式

• 输出若干行。对于每一个操作 $2$，输出对应的结果。

6 3
1 1 4 5 1 4
2 3 5
1 2 5
2 3 5

0
1

10 6
1 3 5 7 8 12 14 15 17 18
2 5 9
1 3 10
2 4 5
1 1 10
2 4 6
2 1 10

0
1
3
0

提示

样例 $3$ 见下发的附件 sequence3.in 和 sequence3.ans。

数据范围及约定

特殊性质 A： 保证对于任意的 $i\in[1,n-1]$，都有 $a_i<a_{i+1}$。
特殊性质 B： 保证没有操作 $1$。

对于全部数据，保证 $1 \leq n,q \leq 6\times10^6$，$a_i,y_i\in[0,10^9]$，$1\le x_i\le n$，$1\le l_i\le r_i \le n$。

提示

本题输入输出量较大，请注意常数因子的影响。

符号解释

• $[P]$ 是艾弗森括号，其中 $P$ 是一个条件。如果 $P$ 为真，则该式子的值为 $1$；否则为 $0$。
• $\min\limits_{i=l}^r\{P\}$ 表示当 $i$ 取 $l,l+1,l+2,\cdots,r$ 时，表达式 $P$ 的取值的最小值；同理定义了 $\max\limits_{i=l}^r\{P\}$。