题解 | 山峰数组计数

import bisect

n = int(input())
nums = list(map(int, input().split()))

# 构建前缀和
sum_nums = [0]
for num in nums:
    sum_nums.append(sum_nums[-1] + num)

total = sum_nums[-1]
cnt = 0

for i in range(1, n):  # 枚举第一段 [0, i)
    b1 = sum_nums[i]

    # 二分查找第一个 j > i，使得 b2 > b1 且 b2 > b3
    left = i + 1
    right = n
    idx_j = -1
    while left <= right:
        mid = (left + right) // 2
        b2 = sum_nums[mid] - sum_nums[i]
        b3 = total - sum_nums[mid]

        if b2 > b1 and b2 > b3:
            idx_j = mid
            right = mid - 1
        else:
            left = mid + 1
    if idx_j != -1:
        cnt += n - idx_j

print(cnt)