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

 

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

 

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

 

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

 

Пример входа

Пример выхода

1

5

1 5 3 6 4

15

 

 

РЕШЕНИЕ

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

 

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

Числа, записанные на ступеньках, являются целыми и ограничены 0 снизу и 106 сверху. Построим дерево Фенвика по массиву a длины 106 + 1 (индексы массива изменяются от 0 до 106 включительно), изначально элементы которого равны нулю. Каждый раз, когда детектив будет проходить ступеньку со значением value, будем увеличивать avalue на value. При этом в дневнике он будет записывать сумму a0 + a1 + a2 + … + avalue-1.

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

 

Пример

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

 

 

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

 

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

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

 

#define MAX 1000001

vector<long long> Fenwick;

 

Вычисление суммы a0 + a1 + ... + ai.

 

long long Summma0_i(int i)

{

  long long result = 0;

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

    result += Fenwick[i];

  return result;

}

 

Увеличение элемента: ai = ai + 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, записанного на ступеньке, увеличиваем avalue на value, а также подсчитываем сумму чисел, записанных ранее на ступеньках и меньших value. Эта сумма равна a0 + a1 + a2 + … + avalue-1.

 

      scanf("%d",&value);

      IncElement(value, value);

      sum += Summma0_i(value-1);

    }

 

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

 

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

  }