Given an array of $$$n \leq 10^5$$$ integers. $$$a_1, a_2, \dots a_n$$$. $$$f(i)$$$ is defined as follows:
Take the first $$$i$$$ elements $$$a_1, a_2, a_3, \dots a_i$$$, sort them in nondecreasing order. Let's call resulting prefix after sort $$$s$$$
Let $$$f(i) = 1 \times s_1 + 2 \times s_2 + 3 \times s_3 + \dots + i \times s_i$$$.
We're asked to calculate $$$f(1) + f(2) + \dots + f(n)$$$ $$$\bmod 10^9 + 7$$$.
Example $$$n = 4$$$ and array $$$[4, 3, 2, 1]$$$
$$$f(1) = 1 \times 4 = 4$$$
$$$f(2) = 1 \times 3 + 2 \times 4 = 11$$$,
$$$f(3) = 1 \times 2 + 2 \times 3 + 3 \times 4 = 20$$$
$$$f(4) = 1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 4 = 30$$$
$$$f(1) + f(2) + f(3) + f(4) = 4 + 11 + 20 + 30 = 65$$$.
Is there a place where I can submit and test my code for it?
Unfortunately no, this problem was in hackerrank problem solving intermediate certification test.
Someone posted it in Leetcode: Link
Suppose you know the value of $$$f(i)$$$, now how can we compute $$$f(i+1)$$$?
Now, assume that there are $$$K$$$ numbers less than or equal to $$$A_{i+1}$$$ and $$$i-K$$$ numbers greater than $$$A_{i+1}$$$ in the $$$i$$$ numbers you have encountered so far.
$$$A_i$$$ will increase the answer by $$$(K+1) * A_{i+1}$$$. For the numbers greater than $$$A_{i+1}$$$, they will increase the overall answer by the sum of all these $$$i-K$$$ numbers. This sum can be kept track of using a Segment Tree.
PS: I haven't tested the solution, so probably take it with a pinch of salt.
Sorry for my poor English and I'm not skilled in LaTeX too.
So think about it, when you have already known $$$f(k)$$$, just insert $$$a_{k+1}$$$ into the sorted list. The contribution to the answer caused by $$$a_{k+1}$$$ is easy to calculate by binary search the sorted list, and then insert $$$a_{k+1}$$$ into it. And you will see, for every element $$$s$$$ in the sorted list, it will shift to the next position when and only when $$$s \geq a_{k+1}$$$.
Thus, $$$f(1) = a_1$$$, and you will see $$$f(k + 1) = f(k) + \sum\limits_{i=1}^{k}\max(a_i, a_{k+1})$$$.
Well you may need some data structures, but I'm not really good at it.
Sorry that I made a big mistake. I thought I have to calculate every single $$$f(k)$$$!
Well, you can see that the answer is
$$$a_1 + \sum\limits_{i=2}^{n}\sum\limits_{j=1}^{i-1}\max(a_i, a_j)$$$ so it will be easy to solve.
This comment itself is the biggest mistake. I don't know how could I think about it.
This can be done using treaps in $$$O(nlogn)$$$