Imbalanced Array (Codeforces 817D)
Tags: Others, divide and conquer

You are given an array a consisting of n elements. The imbalance value of some subsegment of this array is the difference between the maximum and minimum element from this segment. The imbalance value of the array is the sum of imbalance values of all subsegments of this array.For example, the imbalance value of array [1, 4, 1] is 9, because there are 6 different subsegments of this array:   [1] (from index 1 to index 1), imbalance value is 0;  [1, 4] (from index 1 to index 2), imbalance value is 3;  [1, 4, 1] (from index 1 to index 3), imbalance value is 3;  [4] (from index 2 to index 2), imbalance value is 0;  [4, 1] (from index 2 to index 3), imbalance value is 3;  [1] (from index 3 to index 3), imbalance value is 0; You have to determine the imbalance value of the array a.

Input: The first line contains one integer n (1 ≤ n ≤ 106) — size of the array a.The second line contains n integers a1, a2... an (1 ≤ ai ≤ 106) — elements of the array.

Output: Print one integer — the imbalance value of a.


Sample Inputs:
3
1 4 1

Sample Outputs:
9

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

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 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()

    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))

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def add(i, val):
    while i <= n:
        bit[i].append(val)
        i += i & -i

def query(i, x):
    s = 0
    while i > 0:
        pos = bisect.bisect_left(bit[i], x)
        s += len(bit[i]) - pos
        i -= i & -i
    return s
from collections import Counter
import math
bit = []
import bisect
from string import ascii_lowercase as al

def find_max():
    left = []
    st = []
    for i in range(n):
        if not st:
            left.append(-1)
            st.append(i)
        elif st and arr[i] < arr[st[-1]]:
            left.append(st[-1])
            st.append(i)
        else:
            while st and arr[st[-1]] <= arr[i]:
                st.pop()
            if not st:
                st.append(i)
                left.append(-1)
            else:
                left.append(st[-1])
                st.append(i)
    right = []
    st = []
    for i in range(n - 1, -1, -1):
        if not st:
            st.append(i)
            right.append(n)
        elif arr[i] < arr[st[-1]]:
            right.append(st[-1])
            st.append(i)
        else:
            while st and arr[st[-1]] < arr[i]:
                st.pop()
            if st:
                right.append(st[-1])
                st.append(i)
            else:
                right.append(n)
                st.append(i)
    ans = 0
    right = right[::-1]
    for i in range(n):
        x = (right[i] - i) * (i - left[i]) * arr[i]
        if x == 0:
            ans += arr[i]
        else:
            ans += x
    return ans

def find_min():
    left = []
    st = []
    for i in range(n):
        if not st:
            left.append(-1)
            st.append(i)
        elif st and arr[i] > arr[st[-1]]:
            left.append(st[-1])
            st.append(i)
        else:
            while st and arr[st[-1]] >= arr[i]:
                st.pop()
            if not st:
                st.append(i)
                left.append(-1)
            else:
                left.append(st[-1])
                st.append(i)
    right = []
    st = []
    for i in range(n - 1, -1, -1):
        if not st:
            st.append(i)
            right.append(n)
        elif arr[i] > arr[st[-1]]:
            right.append(st[-1])
            st.append(i)
        else:
            while st and arr[st[-1]] > arr[i]:
                st.pop()
            if st:
                right.append(st[-1])
                st.append(i)
            else:
                right.append(n)
                st.append(i)
    ans = 0
    right = right[::-1]
    for i in range(n):
        x = (right[i] - i) * (i - left[i]) * arr[i]
        if x == 0:
            ans += arr[i]
        else:
            ans += x
    return ans
n = int(input())
arr = list(map(int, input().split()))
print(find_max() - find_min())

Solution (Python):
import sys

def pro():
    return sys.stdin.readline().strip()

def rop():
    return map(int, pro().split())

def a_b_b(a, b):
    return a > b

def a_br_b(a, b):
    return a >= b

def a_m_b(a, b):
    return a < b

def a_mr_b(a, b):
    return a <= b

def ry(a, c, t):
    q = len(a)
    x = [(t, -1)]
    r = [0] * q
    for i in range(len(a)):
        v = a[i]
        while c(v, x[-1][0]):
            x.pop()
        r[i] = x[-1][1]
        x.append((v, i))
    return r

def tyr(a):
    q = len(a)
    r = [0] * q
    for i in range(q):
        r[q - i - 1] = q - a[i] - 1
    return r

def main():
    s = int(pro())
    a = list(rop())
    z = a[::-1]
    o = 10 ** 9
    r = 0
    m = ry(a, a_b_b, o)
    n = tyr(ry(z, a_br_b, o))
    b = ry(a, a_m_b, -o)
    v = tyr(ry(z, a_mr_b, -o))
    for i in range(s):
        r += a[i] * ((i - m[i]) * (n[i] - i) - (i - b[i]) * (v[i] - i))
    print(r)
main()

Solution (Python):
n = int(input())
nums = list(map(int, input().split(' ')))
''
larger_right = [n for _ in range(n)]
nums.append(10 ** 5)
mono_s = []
mono_s.append(0)
for i in range(1, n):
    while mono_s and nums[mono_s[-1]] <= nums[i]:
        q = mono_s.pop(-1)
        larger_right[q] = i
    mono_s.append(i)
''
smaller_right = [n for _ in range(n)]
mono_s = []
mono_s.append(0)
for i in range(1, n):
    while mono_s and nums[mono_s[-1]] >= nums[i]:
        q = mono_s.pop(-1)
        smaller_right[q] = i
    mono_s.append(i)
''
larger_left = [-1 for _ in range(n)]
mono_s = []
mono_s.append(n - 1)
for i in range(n - 2, -1, -1):
    while mono_s and nums[mono_s[-1]] < nums[i]:
        q = mono_s.pop(-1)
        larger_left[q] = i
    mono_s.append(i)
''
smaller_left = [-1 for _ in range(n)]
mono_s = []
mono_s.append(n - 1)
for i in range(n - 2, -1, -1):
    while mono_s and nums[mono_s[-1]] > nums[i]:
        q = mono_s.pop(-1)
        smaller_left[q] = i
    mono_s.append(i)
result = 0
for i in range(n):
    result += nums[i] * ((larger_right[i] - i) * (i - larger_left[i]) - (smaller_right[i] - i) * (i - smaller_left[i]))
print(result)