Can someone explain me the approach for the problem:Sums of Sums Thanks:)
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Can someone explain me the approach for the problem:Sums of Sums Thanks:)
Название |
---|
The caveats of the problem are
All numbers in the original array are positive
The final array is sorted
First, instead of getting sum[L, R] in the final sequence, let's get the value of
sum[1, R] - sum[1, L - 1] (this is sometimes called prefix-sums)
Now the problem is that we can't generate the numbers explicitly as there are lots of them, but we can do some two-pointer approach in the original array to count the sum of all subarrays that have sum < = M and how many of them exist in linear time (after choosing M). The idea is to binary search for M. If we want to know sum[1, IDX] in the final array, we must find M such that quantityfinal_array( < = M) < = IDX (we get the sum with the method I will talk below and just add to it (M + 1) * (IDX - (quantityfinal_array( < = M))))
Considering the original array, let's focus on a sum on the interval [L, R]. Let's iterate through the endpoint R to get our quantity of subarrays and the sum of them such that all are good (sum < = M) and end in position R. If sum[L, R] < = M, the sum of [L + 1, R], [L + 2, R], etc will also be good (all numbers in the original array are positive), so we can add to our quantity R - L + 1 and to the sum we add v[L] + 2 * v[L + 1] + 3 * v[L + 2], etc (how many times that numbers are added in a sequence ending in position R) and after that we increase R and do the same thing. If the sum is > M we just increase L. We can get those sums in constant time by adding the appropriates values when increasing R or L (you can refer to my code for details).