4073. Its a Murder!

Once detective Saikat was solving a murder case. While going to the crime scene he took the stairs and saw that a number is written on every stair. He found it suspicious and decides to remember all the numbers that he has seen till now. While remembering the numbers he found that he can find some pattern in those numbers. So he decides that for each number on the stairs he will note down the sum of all the numbers previously seen on the stairs which are smaller than the present number. Calculate the sum of all the numbers written on his notes diary.

Input. First line gives the number of test cases t (t ≤ 10). 2t lines follow. First line gives the number of stairs n (1 ≤ n ≤ 10⁵). Next line gives n numbers written on the stairs. All numbers will be between 0 and 10⁶.

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

Sample input

1

5

1 5 3 6 4

Sample output

15

SOLUTION

data structures – Fenwick tree

Анализ алгоритма

Числа, записанные на ступеньках, являются целыми и ограничены 0 снизу и 10⁶ сверху. Построим дерево Фенвика по массиву a длины 10⁶ + 1 (индексы массива изменяются от 0 до 10⁶ включительно), изначально элементы которого равны нулю. Каждый раз, когда детектив будет проходить ступеньку со значением value, будем увеличивать a_value на value. При этом в дневнике он будет записывать сумму a₀ + a₁ + a₂ + … + a_value-1.

Учитывая ограничения на входные данные, вычисления следует производить в 64-битовом целочисленном типе.

Пример

Промоделируем записи детектива на приведенном примере. Индексация массива начинается с 0. Числа, записываемые детективом, приведены под стрелками.

Сумма чисел, записанных в дневнике детектива, равна 0 + 1 + 1 + 9 + 4 = 15.

Реализация алгоритма

Объявим размер MAX массива а и дерево Фенвика Fenwick.

#define MAX 1000001

vector<long long> Fenwick;

Вычисление суммы 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;

}

Увеличение элемента: a_i = a_i + delta.

void IncElement(int i, int delta)

{

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

Fenwick[i] += delta;

}

Основная часть программы. Читаем входные данные. Заполняем массив Fenwick нулями.

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

Fenwick.assign(MAX,0);

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

{

Для каждого значения value, записанного на ступеньке, увеличиваем a_value на value, а также подсчитываем сумму чисел, записанных ранее на ступеньках и меньших value. Эта сумма равна a₀ + a₁ + a₂ + … + a_value-1.

scanf("%d",&value);

IncElement(value, value);

sum += Summma0_i(value-1);

}

Выводим сумму всех чисел, записанных в дневнике детектива.

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

}