4073. Это убийство!

Однажды детектив Сайкат расследовал дело об убийстве. На месте преступления он обнаружил лестницу, на каждой ступеньке которой было написано число. Детектив счел это подозрительным и решил запомнить все числа, встреченные на пути. Вскоре он заметил закономерность: для каждого числа на лестнице он записывал сумму всех ранее встреченных чисел, которые были меньше текущего.

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

Вход. Первая строка содержит число t (t ≤ 10) – количество тестов. Далее следуют 2t строк. В первой из них указано число n (1 ≤ n ≤ 10⁵) – количество ступенек. В следующей строке записаны n чисел – значения, нанесенные на ступеньки. Все числа находятся в диапазоне от 0 до 10⁶.

Выход. Для каждого теста выведите в отдельной строке итоговую сумму.

Пример входа	Пример выхода
1 5 1 5 3 6 4	15

РЕШЕНИЕ

структуры данных – дерево Фенвика

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

Числа, записанные на ступеньках, являются целыми и находятся в диапазоне от 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;

Функция Summa0_i вычисляет значение суммы 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;

}

Функция IncElement увеличивает значение элемента: a_i = a_i + delta.

void IncElement(int i, int delta)

{

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

Fenwick[i] += delta;

}

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

scanf("%d",&tests);

while (tests--)

{

scanf("%d",&n);

Заполняем массив Fenwick нулями.

Fenwick.assign(MAX,0);

Искомую сумму, записанную в дневнике детектива, будем подсчитывать в переменной sum.

sum = 0;

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

for (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);

}