4073. Its a Murder!

Once, Detective Saikat was investigating a murder case. At the crime scene, he discovered a staircase with a number written on each step. Finding this suspicious, he decided to remember all the numbers he encountered along the way. Soon, he noticed a pattern: for each number on the staircase, he recorded the sum of all previously encountered numbers that were smaller than the current one.

Your task is to find the total sum of all numbers recorded by the detective in his notebook.

Input. The first line contains an integer t (t ≤ 10) – the number of test cases. The next 2t lines follow. The first of these lines contains an integer n (1 ≤ n ≤ 10⁵) – the number of steps. The next line contains n integers – the numbers written on the steps. All numbers are in the range from 0 to 10⁶.

Output. For each test case, print the final sum in a separate line.

Sample input	Sample output
1 5 1 5 3 6 4	15

SOLUTION

data structures – Fenwick tree

Algorithm analysis

The numbers written on the steps are integers and fall within the range from 0 to 10⁶ inclusive.

We will construct a Fenwick tree on an array a of length 10⁶ + 1 (with indices ranging from 0 to 10⁶ inclusive), initially filled with zeros.

Each time the detective steps on a stair with the value value, we increase a_value by value. At the same time, he records the sum in his notebook:

a₀ + a₁ + a₂ + … + a_value-1

Given the input constraints, all calculations should be performed using a 64-bit integer type.

Example

Let’s simulate the detective’s recordings using the given example. The array indexing starts from 0. The numbers recorded by the detective are shown under the arrows.

The sum of the numbers written in the detective’s notebook is

0 + 1 + 1 + 9 + 4 = 15

Algorithm implementation

Let the maximum array size be MAX. Create a Fenwick tree Fenwick.

#define MAX 1000001

vector<long long> Fenwick;

The function Summa0_i computes the sum a₀ + a₁ + ... + a_i.

long long Summma0_i(int i)

{

long long result = 0;

for (; i >= 0; i = (i & (i + 1)) - 1)

result += Fenwick[i];

return result;

}

The function IncElement increases the value of an element: a_i = a_i + delta.

void IncElement(int i, int delta)

{

for (; i < MAX; i = (i | (i+1)))

Fenwick[i] += delta;

}

The main part of the program. Read the input data.

scanf("%d",&tests);

while (tests--)

{

scanf("%d",&n);

Initialize the Fenwick array with zeros.

Fenwick.assign(MAX,0);

The desired sum recorded in the detective’s notebook will be computed in the variable sum.

sum = 0;

Process the numbers written on the steps one by one.

for (i = 0; i < n; i++)

{

For each value written on a step, increase a_value by value and compute the sum of all previously encountered numbers smaller than value. This sum is a₀ + a₁ + a₂ + … + a_value-1.

scanf("%d",&value);

IncElement(value, value);

sum += Summma0_i(value - 1);

}

Print the total sum of all numbers written in the detective’s notebook.

printf("%lld\n",sum);

}