snorkel's blog

By snorkel, history, 3 years ago, In English

How to solve this problem?

Given an array of $$$n \leq 10^5$$$ positive integers ($$$\leq 10^9$$$) and an integer $$$m < 10^{14}$$$, find the subarrays with sum $$$\geq m$$$ and sum up their $$$min \cdot max$$$.

My Idea was to binary search from each position, then for a fixed $$$l$$$ we would have a range $$$[r_{min},n-1]$$$ of valid $$$r$$$-s. And then probably we need some kind of segment tree, but I wasn't able to figure out that.

Source — Problem 2

Thanks.

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

The link you uploaded have expired. Can you repost another version?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a divide and conquer solution but it’s too long to explain here. The brief explanation is this: divide the current segment to 2 subsegments. Calculate the answer of the problem for intervals lying in each left and right subsegments. Now we have to add the sum of the min.max of intervals which contain a part of the right and a part of the left subsegment. for each prefix of the right subsegment (mid, R) calculate these values and store them in some arrays(you can keep them in 1D arrays because we only need to know the rightmost point of the prefix): sum of minimums, sum of maximums, sum of min.max of (mid, mid), (mid, mid + 1), …, (mid, R). Now you can iterate over the L index lying in the left subsegment (and keeping values min and max of (L, mid)) and binary search to find the first R that sum(L, R) >= m and add the sums to the final answer.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    I don't understand the last part. Can you elaborate?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Even if we had to sum up just minimums, I still don't have any idea.

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Here's a draft to a solution: An observation is that r_min decreases while l decreases. So, we will try to calculate a value called sum_mul for every l, which is sum of (min * max) for all r in [r_min, n]. When we reduce l to l — 1, r_min is reduced to new_r_min. For all values from new_r_min to r_min, we can just calculate the answer for each of these positions — we can do this because there are only a total of n "insertions" into the [r_min, n] range. Now for the remaining values: if the (min[l...i] * max[r...i]) value changed when l--, this means that either min[l...i] changes, max[l...i] changes or both.

The idea is that, for all ranges [l1...r1] such that min[l...l1] = min[l...r1] and max[l...l1] = min[r...r1], and min[l...r1] and max[l...r1] is both changed, we will update the answer manually for that range. Then there are some positions left such that only max[l...i]/min[l...i] is changed; and we divide them into ranges such that max[l...i] or min[l...i] (depends on which value is being changed) of these values are previously equal, and then update manually for these ranges. It can be proven that there are only O(n) ranges considered (the logic behind this is similar to that of the monotonic queue).

About how to update on these ranges: the first type is quite trivial. For the second type, you will need to answer a query of the form get_sum for all min[l...i] with i from l1 to r1 (or the equivalent for max), while updating their values with range minimum queries. This can either be done with segment tree beats, or a conventional segment tree supporting the "set range to value i" query, which both works in O(n log n) (the reason why the latter works in O(n log n) is again the same as that of the monotonic queue).

»
3 years ago, # |
Rev. 2   Vote: I like it +75 Vote: I do not like it

We can solve this problem by Divide and Conquer.

$$$F(L, R)$$$ $$$=$$$ $$$\Sigma^{l \le R}_{l = L}$$$$$$\Sigma^{r \le R}_{r=l}$$$ $$$(sum^l_r >= m ? $$$$$$min^l_r$$$ $$$*$$$ $$$max^l_r$$$ $$$:$$$ $$$0)$$$.

We can divide this formula :

$$$mid = \lfloor(l + r)/2\rfloor$$$

$$$F(L, R)$$$ $$$=$$$ $$$F(L, mid)$$$ + $$$F(mid + 1, R)$$$ + $$$\Sigma^{l \le mid}_{l = L}$$$$$$\Sigma^{r \le R}_{r=mid + 1}$$$ $$$(sum^l_r >= m ? $$$$$$min^l_r$$$ $$$*$$$ $$$max^l_r$$$ $$$:$$$ $$$0)$$$.

If we can calculate ($$$\Sigma^{l \le mid}_{l = L}$$$$$$\Sigma^{r \le R}_{r=mid + 1}$$$ $$$(sum^l_r >= m ? $$$$$$min^l_r$$$ $$$*$$$ $$$max^l_r$$$ $$$:$$$ $$$0)$$$) we can solve this problem.

Let's divide this sum in four parts :

1. Minimum at left side, and Maximum at left side
2. Minimum at left side, and Maximum at right side.
3. Minimum at right side, and Maximum at right side.
4. Minimum at right side, and Maximum at left side.

Sum of this $$$4$$$ parts is ($$$\Sigma^{l \le mid}_{l = L}$$$$$$\Sigma^{r \le R}_{r=mid + 1}$$$ $$$(sum^l_r >= m ? $$$$$$min^l_r$$$ $$$*$$$ $$$max^l_r$$$ $$$:$$$ $$$0)$$$).

Thats all. Answer is $$$F(1, n)$$$.

Time : $$$O(nlog^2n)$$$.

(Sorry for my bad english)