Кейсі та Ейпріл#12988

Кейсі та Ейпріл (Розбір)

Розглянемо випадок, коли є лише два числа 0 та 1. Зауважимо, що є 2 випадки:

Тепер для розв’язання початкової задачі використаємо паралельні двійкові пошуки. Будемо йти від менших елементів до більших. Познчатимемо всі менші за поточне значення числа 0, а всі більші чи рівні 1. Таким чином ми звели задачу до запитів зміни 1 на 0 і знаходження, найближчих до певної позиції, двох однакових чисел підряд. Цю задачу можна розв’язувати за допомогою системи неперетинних множин. Для зручності числа можна стиснути.

Складність: O(n \log n).