Розглянемо випадок, коли є лише два числа 0 та 1. Зауважимо, що є 2 випадки:
Коли немає двох підряд однакових елементів. Тоді на кожному кроці 0 заміниться на 1, а 1 на 0. Ми можемо легко визначити що де буде, через парність числа .
Коли є два підряд однакових елементи. Проміжки з однакових елементів будуть розширюватися на 1 в кожен бік, поки не зустрінуть інший такий проміжок. Відповідно для позиції ми можемо визначити що в ній буде, якщо знайдемо найближчий проміжок з двох однакових справа та зліва. Якщо малень і жоден з проміжків не встигне розширитися, то ми можемо визначити що буде в цій позиції через парність (як у першому випадку).
Тепер для розв’язання початкової задачі використаємо паралельні двійкові пошуки. Будемо йти від менших елементів до більших. Познчатимемо всі менші за поточне значення числа 0, а всі більші чи рівні 1. Таким чином ми звели задачу до запитів зміни 1 на 0 і знаходження, найближчих до певної позиції, двох однакових чисел підряд. Цю задачу можна розв’язувати за допомогою системи неперетинних множин. Для зручності числа можна стиснути.
Складність: O(n \log n).