Lipshitz Sequence (Codeforces 601B)
Tags: Math, data structures

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:  if n < 2,   if n ≥ 2,  over all 1 ≤ i < j ≤ n 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 .

Note: In the first query of the first sample, the Lipschitz constants of subarrays of  with length at least 2 are:       The answer to the query is their sum.

Sample Inputs:
10 4
1 5 2 9 1 3 4 2 1 7
2 4
3 8
7 10
1 9

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

Sample Outputs:
17
82
23
210

2
0
22
59
16
8

Solution (Python):
def read_data():
    (n, q) = map(int, input().split())
    As = list(map(int, input().split()))
    LRs = []
    for i in range(q):
        (L, R) = list(map(int, input().split()))
        LRs.append((L, R))
    return (n, q, As, LRs)

def solve(n, q, As, LRs):
    difs = calc_difs(As)
    Ls = get_Ls(difs)
    Rs = get_Rs_allow_ties(difs)
    for (L, R) in LRs:
        print(calc(L - 1, R - 2, Ls, Rs, difs))

def calc_difs(As):
    difs = [abs(a0 - a1) for (a0, a1) in zip(As, As[1:])]
    return difs

def get_Ls(Vs):
    L = []
    st = []
    for (i, v) in enumerate(Vs):
        while st and Vs[st[-1]] < v:
            st.pop()
        if st:
            L.append(st[-1] + 1)
        else:
            L.append(0)
        st.append(i)
    return L

def get_Ls_allow_ties(Vs):
    L = []
    st = []
    for (i, v) in enumerate(Vs):
        while st and Vs[st[-1]] <= v:
            st.pop()
        if st:
            L.append(st[-1] + 1)
        else:
            L.append(0)
        st.append(i)
    return L

def get_Rs(Vs):
    n = len(Vs)
    revVs = Vs[::-1]
    revRs = get_Ls(revVs)
    revRs.reverse()
    return [n - 1 - R for R in revRs]

def get_Rs_allow_ties(Vs):
    n = len(Vs)
    revVs = Vs[::-1]
    revRs = get_Ls_allow_ties(revVs)
    revRs.reverse()
    return [n - 1 - R for R in revRs]

def calc(L, R, Ls, Rs, difs):
    ans = 0
    for i in range(L, R + 1):
        ans += difs[i] * (i - max(Ls[i], L) + 1) * (min(Rs[i], R) - i + 1)
    return ans
(n, q, As, LRs) = read_data()
solve(n, q, As, LRs)

Solution (Python):
f = lambda : map(int, input().split())
(n, m) = f()
t = list(f())
p = [1000000000.0] + [abs(b - a) for (a, b) in zip(t, t[1:])] + [1000000000.0]
(L, R) = ([0] * n, [0] * n)
for i in range(1, n):
    j = n - i
    (x, y) = (i - 1, j + 1)
    (a, b) = (p[i], p[j])
    while a > p[x]:
        x = L[x]
    while b >= p[y]:
        y = R[y]
    (L[i], R[j]) = (x, y)
for k in range(m):
    (l, r) = f()
    print(sum(((i - max(l - 1, L[i])) * (min(r, R[i]) - i) * p[i] for i in range(l, r))))

Solution (Python):
f = lambda : map(int, input().split())
(n, m) = f()
t = list(f())
p = [1000000000.0] + [abs(b - a) for (a, b) in zip(t, t[1:])] + [1000000000.0]
(L, R) = ([0] * n, [0] * n)
for i in range(1, n):
    j = n - i
    (x, y) = (i - 1, j + 1)
    (a, b) = (p[i], p[j])
    while a > p[x]:
        x = L[x]
    while b >= p[y]:
        y = R[y]
    (L[i], R[j]) = (x, y)
for k in range(m):
    (l, r) = f()
    print(sum(((i - max(l - 1, L[i])) * (min(r, R[i]) - i) * p[i] for i in range(l, r))))