Need help with a simple Divide and Conquer problem

Revision en2, by heavenly_, 2024-09-11 12:05:19

Hi, I have this DnC problem, I would greatly appreciate any help, thank you!

Given an array a with n elements, calculate the sum of min * max over every ranges [l, r] (1 <= l <= r <= n)

Constraints:

1 <= n <= 1e5, 1 <= a_i <= 1e9

Sample test:

4

1 4 3 1

Answer: 58

Tags divide and conquer

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English heavenly_ 2024-09-11 12:05:19 4 Tiny change: 'le test:\n4\n1 4 3 1\' -> 'le test:\n\n4\n\n1 4 3 1\'
en1 English heavenly_ 2024-09-11 12:04:39 331 Initial revision (published)