[Python] P6503 [COCI 2010/2011 #3] DIFERENCIJA

发表于 分类于

给出一个长度为 n 的序列 ai，求出下列式子的值：

$$\sum_{i=1}^{n} \sum_{j=i}^{n} (\max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k)$$

即定义一个子序列的权值为序列内最大值与最小值的差。求出所有连续子序列的权值和。

输入格式

输入第一行一个整数 n，表示序列的长度。

接下来的 n 行，每行一个整数 ai，描述这个序列。

输出格式

输出一行一个整数，表示式子的答案。

输入输出样例 #1

输入 #1

1
2
3
4
3
1
2
3

输出 #1

1
4

输入输出样例 #2

输入 #2

1
2
3
4
5
4
7
5
7
5

输出 #2

1
12

输入输出样例 #3

输入 #3

1
2
3
4
5
4
3
1
7
2

输出 #3

1
31

说明/提示

数据规模与约定

对于 100% 的数据，保证 2 ≤ n ≤ 3 × 105，1 ≤ ai ≤ 108。

说明

题目译自 COCI2010-2011 CONTEST #3 T5 DIFERENCIJA。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def calculate_contributions(arr, is_max=True):
    n = len(arr)
    left = [-1] * n  # 左侧第一个大于(小于)当前元素的索引
    right = [n] * n  # 右侧第一个大于等于(小于等于)当前元素的索引
    stack = []
    
    # 寻找左侧边界
    for i in range(n):
        if is_max:
            # 对于最大值，寻找左侧第一个大于当前元素的位置
            while stack and arr[stack[-1]] <= arr[i]:
                stack.pop()
        else:
            # 对于最小值，寻找左侧第一个小于当前元素的位置
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
        
        if stack:
            left[i] = stack[-1]
        stack.append(i)
    
    stack = []
    # 寻找右侧边界
    for i in range(n-1, -1, -1):
        if is_max:
            # 对于最大值，寻找右侧第一个大于等于当前元素的位置
            while stack and arr[stack[-1]] < arr[i]:
                stack.pop()
        else:
            # 对于最小值，寻找右侧第一个小于等于当前元素的位置
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
        
        if stack:
            right[i] = stack[-1]
        stack.append(i)
    
    # 计算总贡献
    total = 0
    for i in range(n):
        # 左侧可扩展的距离
        left_count = i - left[i]
        # 右侧可扩展的距离
        right_count = right[i] - i
        # 贡献 = 元素值 × 以该元素为最大(小)值的子序列数量
        total += arr[i] * left_count * right_count
    
    return total

n = int(input())
arr = [int(input()) for _ in range(n)]

# 结果 = 所有最大值贡献和 - 所有最小值贡献和
result = calculate_contributions(arr, True) - calculate_contributions(arr, False)
print(result)