Задачи
Динамическая инверсия
Динамическая инверсия
Задана перестановка {1, 2, 3, ..., n}. Удалите из нее m элементов один за одним, и выведите количество пар инверсий перед каждым удалением. Количество пар инверсий в массиве a равно числу упорядоченных пар (i, j) таких что i < j и a[i]
> a[j]
.
Входные данные
Состоит из нескольких тестов. Первая строка каждого теста содержит два целых числа n и m (1 ≤ n ≤ 2 * 10^5
, 1 ≤ m ≤ 10^5
). Далее n строк задают начальную перестановку. Следующие m строк задают удаляемые числа в порядке их удаления. Ни одно число не удаляется дважды.
Выходные данные
Для каждого удаления вывести количество пар инверсий перед ним.
Пример
(1, 5, 3, 4, 2) -> (1, 3, 4, 2) -> (3, 4, 2) -> (3, 2) -> (3)
Пример
Входные данные #1
5 4 1 5 3 4 2 5 1 4 2
Выходные данные #1
5 2 2 1