Сходинкові закономірності#4073

Сходинкові закономірності (Розбір)

Числа, записані на сходинках, є цілими і знаходяться в діапазоні від $0$ до $1 0^{6}$ 10^6 включно. Побудуємо дерево Фенвіка на масиві $a$ довжини $1 0^{6} + 1$ 10^6 + 1 (індекси масиву змінюються від $0$ до $1 0^{6}$ 10^6 включно), яке спочатку заповнено нулями.

Кожного разу, коли детектив проходить сходинку зі значенням $v a l u e$ , збільшуємо $a_{v a l u e}$ a_{value} на $v a l u e$ . При цьому в щоденнику він запише суму:

a_{0} + a_{1} + a_{2} + ... + a_{v a l u e - 1}

a_0 + a_1 + a_2 + ... + a_{value - 1}

З урахуванням обмежень на вхідні дані, всі обчислення слід виконувати в $64$ -бітовому цілочисельному типі.

Приклад

Смоделюємо записи детектива на наведеному прикладі. Індексація масиву починається з $0$ . Числа, записані детективом, вказані під стрілками.

Сума чисел, записаних у щоденнику детектива, дорівнює

0 + 1 + 1 + 9 + 4 = 15

0 + 1 + 1 + 9 + 4 = 15

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

Нехай максимальний розмір масиву дорівнює $M A X$ . Створимо дерево Фенвіка $F e n w i c k$ Fenwick.

#define MAX 1000001
vector<long long> Fenwick;

Функція Summa0_i обчислює значення суми $a_{0} + a_{1} + ... + a_{i}$ a_0 + a_1 + ... + 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;
}

C++

Функція IncElement збільшує значення елемента: $a_{i} = a_{i} + d e l t a$ 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);

Заповнюємо масив $F e n w i c k$ Fenwick нулями.

  Fenwick.assign(MAX,0);

Шукану суму, записану в щоденнику детектива, підраховуватимемо в змінній $s u m$ .

  sum = 0;

Послідовно обробляємо числа, записані на сходинках.

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

Для кожного значення $v a l u e$ , записаного на сходинці, збільшуємо $a_{v a l u e}$ a_{value} на $v a l u e$ , а також обчислюємо суму всіх раніше зустрінутих чисел, менших за $v a l u e$ . Ця сума дорівнює $a_{0} + a_{1} + a_{2} + ... + a_{v a l u e - 1}$ a_0 + a_1 + a_2 + ... + a_{value - 1}.

    scanf("%d",&value);
    IncElement(value, value);
    sum += Summma0_i(value - 1);
  }

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

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