PermutatioN#12853

PermutatioN (Editorial)

Помітимо спершу, що задача, по суті, просить порахувати нас кількість таких відрізків , що p_i та p_j це максимальний та мінімальний елемент серед чисел p_i, p_{i+1}, \ldots, p_j (в якомусь порядку). Дійсно: у всіх таких відрізків пари різні, а для відрізку , для якого умова вище не виконується, пара співпадає з парою (i_1, j_1), де i_1, j_1 — позиції мінімуму та максимуму на цьому відрізку.

Будемо називати такі відрізки хорошими. Очевидно, всі відрізки хороші.

Порахуємо спершу кількість відрізків з i<j, для яких p_i мінімальне серед p_i, p_{i+1}, \ldots, p_j, а p_j максимальне, а потім агалогічно порахуємо ті, для яких p_i максимальне і p_j мінімальне.

Для початку для кожного порахуємо мінімальне lim_i, що p_i — максимальне серед p[lim_i:i]. Це класична задача, і це можна зробити одним проходом зі стеком.

Тепер будемо йти зліва направо і тримати в стеці лише такі позиції , що справа від них (до моменту, який ми розглядаємо наразі) немає елементів, менших за них. Нехай зараз ми обробляємо елемент p_i. Спершу ми видаляємо зі стеку останню позицію , поки p_x>p_i. Тепер, для кожного , що лишився в стеку, p_x є мінімумом на p[x:i], і всі такі , для яких p_x є мінімумом на p[x:i], лежать в стеці. Нам лишилось знайти, для скількох з цих p_j є максимумом на p[x:j].

Це рівносильно тому, що ми хочемо знайти кількість позицій в стеці, що не менші за lim_i. Це просто зробити бінарним пошуком (за умови, якщо ми пишемо стек на масиві), адже позиції в стеку відсортовані.

Загальна асимптотика O(n\log{n}).