Interesting range query problem

Правка en2, от snorkel, 2021-10-12 17:54:48

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский snorkel 2021-10-12 17:54:48 86
en1 Английский snorkel 2021-10-12 12:39:42 567 Initial revision (published)