Interesting range query problem

Revision en1, by snorkel, 2021-10-12 12:39:42

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English snorkel 2021-10-12 17:54:48 86
en1 English snorkel 2021-10-12 12:39:42 567 Initial revision (published)