Codeforces Round #333 (Div. 2) D. Lipshitz Sequence （单调栈）
Codeforces Round #333 (Div. 2) D. Lipshitz Sequence （单调栈）
D. Lipshitz Sequence
time limit per test
memory limit per test
input
output
A function
is called Lipschitz continuous if there is a real constant K such that the inequality |f(x) - f(y)| ≤ K·|x - y| holds for all
. We'll deal with a more... discrete version of this term.For an array
, we define it's Lipschitz constant
as follows:
In other words,
is the smallest non-negative integer such that |h[i] - h[j]| ≤ L·|i - j| holds for all 1 ≤ i, j ≤ n.You are given an array
of size n and q queries of the form [l, r]. For each query, consider the subarray
; determine the sum of Lipschitz constants of all subarrays of
.
Input
The first line of the input contains two space-separated integers n and q (2 ≤ n ≤ 100 000 and 1 ≤ q ≤ 100) — the number of elements in array
and the number of queries respectively.The second line contains n space-separated integers
(
).
The following q lines describe queries. The i-th of those lines contains two space-separated integers li and ri (1 ≤ li < ri ≤ n).
Output
Print the answers to all queries in the order in which they are given in the input. For the i-th query, print one line containing a single integer — the sum of Lipschitz constants of all subarrays of
.
Examples
input
10 41 5 2 9 1 3 4 2 1 72 43 87 101 9
output
178223210
input
7 65 7 7 4 6 6 21 22 32 61 74 73 5
output
202259168
Note
In the first query of the first sample, the Lipschitz constants of subarrays of
with length at least 2
The answer to the query is their sum.
题意：给你一组数，q个询问，每次询问一个区间。让你求出这个区间中各个子区间中相邻两个数绝对值的最大值之和。
题解：预处理一下。然后单调栈乱搞一下就可以了。
代码：
#pragma comment(linker, "/STACK:102400000,102400000")//#include
相关文章
发表评论
暂时没有评论，来抢沙发吧~