← 返回题目列表

Codeforces · 601/B

B. 利普希茨序列

中文机器翻译题面 查看原题

如果存在实数常数 K 且不等式 |f(x) - f(y)|,则函数 $$f : \mathbb{R} \to \mathbb{R}$$ 称为 Lipschitz 连续函数≤ K·|x - y|对于 \mathbb{R}$$ 中的所有 $$x,y 成立。我们将处理这个术语的一个更......离散的版本。

对于数组 $$h[1..n]$$,我们定义它的 Lipschitz 常量 $${\cal L}({\bf h})$$ 如下:

- 如果 n < 2,$$L(\mathbf{h}) = 0$$
- 如果 n ≥ 2,$${\displaystyle L(h)=\max \left\{{\frac {|h[j]-h[i]|}{j-i}}\right\}}$$ 超过所有 1 ≤ i < j ≤ n

换句话说,$$L = L(h)$$ 是满足 |h[i] - h[j]| 的最小非负整数。 ≤ L·|i - j|对于所有 1 ≤ i, j ≤ n 成立。

给定一个大小为 n 的数组 $$\alpha$$ 和 [l, r] 形式的 q 个查询。对于每个查询,考虑子数组 $$s = a[l..r]$$;确定 ? 的所有子数组的 Lipschitz 常数之和。

输入

输入的第一行包含两个空格分隔的整数 n 和 q(2 ≤ n ≤ 100 000 和 1 ≤ q ≤ 100)——分别是数组 $$\alpha$$ 中的元素数量和查询数量。

第二行包含 n 个空格分隔的整数 $${\mathbf{a}}^{[1..n]}$$ ($$0 \leq a[i] \leq 10^8$$)。

以下 q 行描述查询。这些行的第 i 行包含两个空格分隔的整数 li 和 ri (1 ≤ li < ri ≤ n)。

输出

按照输入中给出的顺序打印所有查询的答案。对于第 i 个查询,打印一行,其中包含一个整数 - $$a[l_i..r_i]$$ 的所有子数组的 Lipschitz 常量之和。

示例

输入 #1

10 4
1 5 2 9 1 3 4 2 1 7
2 4
3 8
7 10
1 9

输出 #1

17
82
23
210

输入 #2

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

输出 #2

2
0
22
59
16
8

注意

在第一个样本的第一个查询中,长度至少为 2 的 $$[5,2,9]$$ 子数组的 Lipschitz 常量为:

- $${\cal L}([5,2])=3$$
- $$L([2,9])=7$$
- $$L([5,2,9])=7$$

查询的答案是它们的总和。