heavenly_'s blog

Need help with a simple Divide and Conquer problem
By heavenly_, history, 2 months ago, In English

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

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In case anyone wants to submit their solution, the problem is here. (with n <= 3e5)

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a rough outline for how you can find the answer for all subsegments which cover index $$$m = (l + r)/2$$$ for fixed subsegment $$$[l, r]$$$ in your recursion:

  1. Build suffix min/max array for $$$[l, m]$$$ and prefix min/max for $$$[m, r]$$$. Also build suffix sum array of suffix maximums of $$$[l, m]$$$ and analogous prefix array for $$$[m, r]$$$.
  2. First, we find the sum for segments for which minimum lies in left half. Iterate over suffix $$$s$$$ of left half. Let suffix minimum of $$$s$$$ be $$$x$$$. Now, you can only include prefixes from right half which have minimum $$$\geq x$$$ (there will exist some $$$j$$$ such that all prefixes with length $$$\leq j$$$ in right half will have minimum $$$\geq x$$$, find this by binary search). There will also exist some $$$k \leq j$$$ such that the prefix maximum of all prefixes in right half with length $$$\leq k$$$ will be smaller than the suffix maximum of $$$s$$$ (find this with binary search too). Now simply add the contribution of this suffix (using the arrays you built).
  3. Process the case when minimum lies in right half symmetrically (note that you need to carefully handle the case where minimum from both halves is equal).
→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry, I'm a bit unclear on this part:

    here will also exist some k≤j such that the prefix maximum of all prefixes in right half with length ≤k will be smaller than the suffix maximum of s (find this with binary search too)

    What if the prefix maximum is strictly increasing and always larger than the suffix that lies on [l, m] and the minimum of the right part is always smaller than that of the left side? won't this yield O((m — l + 1) * (r — m)) time complexity for that block alone?

    Edit: I got it, since we already calculated prefix sum, we won't have this problem, thank you

    → Reply