折叠
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

本题没有题目背景，请自己脑补。

现有长为 n 的正整数数列 \{a_n\}，你需要维护一个数据结构，有两种操作：

1.输入 l,r(1\leqslant l\leqslant r\leqslant n)，输出 a_l,a_{l+1},a_{l+2}\cdots,a_{r-1},a_r 这段“从左向右展开”的结果，即
a_l+\left|a_l-a_{l+1}\right|+\left|a_{l+1}-a_{l+2}\right|+\cdots+\left|a_{r-1}-a_r\right|.

2.输入 l,r(1<l\leqslant r<n)，让 a_i\leftarrow a_i+1,l\leqslant i\leqslant r，即让下标位于 [l,r] 范围内的元素 a_i 的值加一。

输入描述:

第一行两个整数 n,q(1\leqslant n,q\leqslant 2\times 10^{5})，分别表示原始数列长度和操作个数。

第二行 n 个正整数 a_i，满足 1\leqslant a_i\leqslant 10^4。

接下来 q 行，每行三个正整数 opt(opt=1,2),l,r，对应上述的操作。

输出描述:

对于每个操作 1，输出一个数表示结果，一个结果占一行。
示例1

输入

复制 
5 3
1 3 2 4 5
1 1 5
2 2 4
1 1 5

输出

复制 
7
7

说明

初始时，数列为 1,3,2,4,5。

操作 1，输出 1+|1-3|+|3-2|+|2-4|+|4-5|=7。

操作 2，修改数列为 1,4,3,5,5。

操作 1，输出 1+|1-4|+|4-3|+|3-5|+|5-5|=7。

备注:

注：遇到 l=r 的情况：对于操作 1 你只需输出 a_l；对于操作 2 你只需修改 a_l。

如果 Python3 提交超时的话可以尝试提交 PyPy3。