When There Is Nothing to Do and Only a Permutation at Home#12857

When There Is Nothing to Do and Only a Permutation at Home (Editorial)

Порахуємо спершу, скільки секунд займе ітерація для перестановки вигляду (k, 1, 2, \ldots, k-1, k+1, \ldots, n). При k>1 попередня перестановка до неї — (k-1, n, n-1, \ldots, k, k-2, \ldots, 2, 1). Можна помітити, що в цій перестановці не змінився порядок лише таких пар елементів: (k-1, k+1), (k-1, k+2), \ldots, (k-1, n), а також (k, 1), (k, 2), \ldots, (k, k-2). Всього не змінився порядок рівно в (n-k) + (k-2) = (n-2) пар, а отже для кожної з інших \frac{n(n-1)}{2} - (n-2) пар буде операція, в якій ми міняємо місцями числа з цієї пари. Таким чином, ця ітерація займає \frac{n(n-1)}{2} - (n-2) = cnt_n

Порахуємо спершу dp_n — за скільки секунд перестановка (n, n-1, n-2, \ldots, 1) перетвориться на перестановку (1, 2, 3, \ldots, n). Спершу ми витратимо dp_{n-1} секунд, щоб отримати (n, 1, 2, \ldots, n-1), а далі ми n-1 разів будемо виконувати перехід з першого абзацу (витрачаючи по cnt_n секунд), і n-1 разів сортувати останні n-1 елемент. Всього маємо dp_n = (n-1)cnt_n + ndp_{n-1}.

Тепер будемо йти справа наліво. Нехай на цю мить в нас відсортовані елементи від p_{n-x+1} до p_n в порядку зростання. Тоді, якщо p_{n-x} більше за рівно чисел з p_{n-x+1} до p_n, то за t(cnt_{x+1} + dp_x) стануть відсортованими і числа від p_{n-x} до p_n. Порахувати це можна з допомогою дерева відрізків/Фенвіка/orderedset.

Просумуємо це по всім і отримаємо відповідь.