Consider the following algorithm that solves the problem for each \(i\), which is a direct translation of the problem statement:

for i = 1 to N:
  sum = 0
  for j = 1 to N:
    if A[j] > A[i]:
      sum += A[j]
  ans[i] = sum

This algorithm costs \(\Theta(N^2)\) time, so it is difficult to meet the execution time limit. Let us consider a more efficient way.

Here, we first consider the case where the elements of \(A\) are pairwise distinct.

If the elements of \(A\) are sorted in descending order, the answer for each \(i\) can be found in ascending order of \(i\). That is, if \(A=(8,6,5,3,1)\),

• For \(i=1\), the sum of elements greater than \(A_1=8\) is \(0\).
• For \(i=2\), the sum of elements greater than \(A_2=6\) is \(8\).
• For \(i=3\), the sum of elements greater than \(A_3=5\) is \(8+6\).
• For \(i=4\), the sum of elements greater than \(A_4=3\) is \(8+6+5\).
• For \(i=5\), the sum of elements greater than \(A_5=1\) is \(8+6+5+3\).

Thus, the answer can be found in a total of \(O(N)\) time.

sum = 0
for i = 1 to N:
  ans[i] = sum
  sum += A[i]

The key of this algorithm is that, by processing \(A\) in descending order, the set of elements greater than the current element monotonically increases, so that one can only update the difference. Even if \(A\) is not in descending order, one can process the queries in an order such that the inspected elements are in descending order. That is, if \(A=(3,8,6,1,5)\), one can solve the problem in the following order:

• For \(i=2\), the sum of elements greater than \(A_2=8\) is \(0\)
• For \(i=3\), the sum of elements greater than \(A_3=6\) is \(8\)
• For \(i=5\), the sum of elements greater than \(A_5=5\) is \(8+6\)
• For \(i=1\), the sum of elements greater than \(A_1=3\) is \(8+6+5\)
• For \(i=4\), the sum of elements greater than \(A_4=1\) is \(8+6+5+3\)

In order to obtain such an order, for example one can sort the pairs (tuples) \((A_i,i)\).

value_index = [(A[1], 1), (A[2], 2), ..., (A[N], N)]
Sort value_index in descending order
sum = 0
for k = 1 to N:
  Ai, i = value_index[k]
  ans[i] = sum
  sum += Ai

The sort requires \(O(N\log N)\) time, so the solution costs \(O(N \log N)\) time.

Even if \(A\) contains the same value, one can similarly solve the problem, with extra caution on when to update sum in the algorithm above. A simpler way is to handle “pair of value and list of indices” instead of “pair of value and index.” For more details, see the writer’s solution below.

Writer’s solution (C++)

Writer’s solution (Python)