Lipshitz Sequence (Codeforces 602D)
Tags: Math, math

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):
import sys

class FastIO:

    def __init__(self):
        return

    @staticmethod
    def read_str():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def read_int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def read_float():
        return float(sys.stdin.readline().rstrip())

    @staticmethod
    def read_ints():
        return map(int, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_floats():
        return map(float, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_ints_minus_one():
        return map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_list_ints():
        return list(map(int, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_floats():
        return list(map(float, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_ints_minus_one():
        return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_strs():
        return sys.stdin.readline().rstrip().split()

    @staticmethod
    def read_list_str():
        return list(sys.stdin.readline().rstrip())

    @staticmethod
    def st(x):
        return print(x)

    @staticmethod
    def lst(x):
        return print(*x)

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def accumulate(nums):
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        return pre

class Solution:

    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        (n, q) = ac.read_ints()
        nums = ac.read_list_ints()
        diff = [abs(nums[i + 1] - nums[i]) for i in range(n - 1)]
        post = [n - 2] * (n - 1)
        pre = [0] * (n - 1)
        stack = []
        for i in range(n - 1):
            v = diff[i]
            while stack and stack[-1][1] < v:
                post[stack.pop()[0]] = i - 1
            if stack:
                pre[i] = stack[-1][0] + 1
            stack.append([i, v])
        for _ in range(q):
            (l, r) = ac.read_ints_minus_one()
            ans = 0
            for i in range(l, r):
                ans += diff[i] * (i - ac.max(l, pre[i]) + 1) * (ac.min(post[i], r - 1) - i + 1)
            ac.st(ans)
        return
Solution().main()

Solution (Python):
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
(n, q) = MII()
nums = LII()
diff = [abs(y - x) for (x, y) in zip(nums, nums[1:])]
left_smaller = [None] * (n - 1)
stack = [(-1, inf)]
for i in range(n - 1):
    v = diff[i]
    while stack[-1][1] <= v:
        stack.pop()
    left_smaller[i] = stack[-1][0]
    stack.append((i, v))
right_smaller = [None] * (n - 1)
stack = [(n, inf)]
for i in range(n - 2, -1, -1):
    v = diff[i]
    while stack[-1][1] < v:
        stack.pop()
    right_smaller[i] = stack[-1][0]
    stack.append((i, v))
for _ in range(q):
    (l, r) = GMI()
    ans = 0
    for i in range(l, r):
        ans += diff[i] * (i - max(l - 1, left_smaller[i])) * (min(r, right_smaller[i]) - i)
    print(ans)

Solution (Python):
import sys

class FastIO:

    def __init__(self):
        return

    @staticmethod
    def read_str():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def read_int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def read_float():
        return float(sys.stdin.readline().rstrip())

    @staticmethod
    def read_ints():
        return map(int, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_floats():
        return map(float, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_ints_minus_one():
        return map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_list_ints():
        return list(map(int, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_floats():
        return list(map(float, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_ints_minus_one():
        return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_strs():
        return sys.stdin.readline().rstrip().split()

    @staticmethod
    def read_list_str():
        return list(sys.stdin.readline().rstrip())

    @staticmethod
    def st(x):
        return print(x)

    @staticmethod
    def lst(x):
        return print(*x)

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def accumulate(nums):
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        return pre

class Solution:

    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        (n, q) = ac.read_ints()
        nums = ac.read_list_ints()
        diff = [abs(nums[i + 1] - nums[i]) for i in range(n - 1)]
        post = [n - 2] * (n - 1)
        pre = [0] * (n - 1)
        stack = []
        for i in range(n - 1):
            while stack and diff[stack[-1]] < diff[i]:
                post[stack.pop()] = i - 1
            if stack:
                pre[i] = stack[-1] + 1
            stack.append(i)
        for _ in range(q):
            (l, r) = ac.read_ints_minus_one()
            ans = 0
            for i in range(l, r):
                ans += diff[i] * (i - ac.max(l, pre[i]) + 1) * (ac.min(post[i], r - 1) - i + 1)
            ac.st(ans)
        return
Solution().main()