Войти Регистрация
Алгоритмы

107. Переводы, пришедшие не по порядку

Сложная

Перевод получает номер при создании, а в процессинг приходит позже, и очередь шин его иногда перемешивает. ids — номера переводов в порядке прихода. Номера могут повторяться: повтор — это ретрай того же перевода.

Пара позиций i < j «пришла не по порядку», если ids[i] > ids[j]. Равные номера парой не считаются.

Верните число таких пар — по нему мониторинг решает, не пора ли включать пересортировку на входе.

В работе: Метрика беспорядка в очереди переводов: 0 — всё пришло по порядку, n·(n−1)/2 — ровно наоборот.

Пример 1

Ввод
ids = [3, 1, 2, 5, 4]
Вывод
3

Пары (3, 1), (3, 2), (5, 4) — итого 3.

Пример 2

Ввод
ids = [7, 7, 7]
Вывод
0

Ретраи одного перевода не нарушают порядок.

Ограничения

  • 0 ≤ n ≤ 10⁵
  • 1 ≤ ids[i] ≤ 10¹²
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def late_transfers(ids):
Дерево ФенвикаСжатие координатИнверсиицельO(n log n)

Источник: наша задача на данных Т-Банка. Условие пересказано своими словами.