Автор: Костянтин Денисов
Розробник: Андрій Холод
Розбір підготовано: Костянтин Денисов
Маємо бінарний масив a_1,\dots,a_n. Операція: вибрати підвідрізок довжини , у якому рівно нулів і одиниць, та перефарбувати всі нулі в одиниці. Підвідрізок називається гарним, якщо можна зробити всі його елементи рівними .
1. Розглянемо весь масив.
За одну операцію кількість нулів зменшується рівно на , тому загальна кількість нулів повинна ділитися на .
Нехай позиції нулів у масиві дорівнюють p_0 < p_1 < \dots < p_{m-1}.
Пояснимо, чому нулі неминуче розбиваються саме на послідовні блоки p_0,\dots,p_{k-1}, потім p_k,\dots,p_{2k-1} і так далі.
Припустимо, що ми зробили операцію на нулях p_i,p_{i+1},\dots,p_{i+k-1}, де не кратне . Тоді ліворуч від цього блока залишиться рівно нулів. Оскільки не кратне і посередині з'явився блок з одиниць, то це значить ці нулів неможливо буде повністю покрити операціями по нулів, бо не можна зробити операцію, де є частина нулів зліва від операції та справа. Тобто масив вже ніколи не стане повністю з одиниць.
Отже, кожна операція зобов'язана брати нулі так, щоб кількість нулів ліворуч від них залишалася кратною . Це означає, що нулі можуть фарбуватися тільки блоками p_{jk}, p_{jk+1}, \dots, p_{jk+k-1}.
Тепер для кожного такого блока необхідно, щоб він взагалі поміщався у підвідрізок довжини . Тобто для кожного має виконуватись p_{jk+k-1} - p_{jk} + 1 \le 2k. Якщо для якогось блока це не так, то його неможливо пофарбувати жодним ходом.
Залишилась ще одна умова. Навіть якщо кожен блок по нулів поміщається в , потрібно, щоб існував хоча б один блок, який можна зробити першим ходом.
Нехай блок починається в p_t і закінчується в p_{t+k-1}. Позначимо:
— позиція попереднього нуля перед p_t (або , якщо його немає),
— позиція наступного нуля після p_{t+k-1} (або , якщо його немає).
У проміжку [L+1, R-1] знаходяться рівно ці нулів і більше жодних. Щоб можна було зробити хід саме на цьому блоці, потрібно, щоб у цьому проміжку існував підвідрізок довжини . Тобто повинно виконуватись R - L - 1 \ge 2k.
Якщо існує хоча б один блок, для якого це виконується, то можна зробити перший хід. Після цього утворюється відрізок довжини , що складається лише з одиниць, і далі з нього можна поступово пофарбувати всі сусідні блоки зліва і справа.
Отже, масив гарний тоді і тільки тоді, коли:
кількість нулів ділиться на ;
для кожного блока p_{jk},\dots,p_{jk+k-1} виконується p_{jk+k-1} - p_{jk} + 1 \le 2k;
існує хоча б один блок, для якого R - L - 1 \ge 2k.
2. Запити [l,r].
Для підвідрізка логіка повністю аналогічна, тільки крайні блоки можуть використовувати межі або .
Попередньо зберігаємо позиції всіх нулів у масиві p_0<p_1<\dots<p_{m-1}. Також зберігаємо:
номер нуля для кожної позиції масиву;
для кожної позиції масиву індекс найближчого нуля праворуч.
Для кожного можливого старту блока (кожного p_t) визначимо тип:
тип , якщо блок із нулів не існує або p_{t+k-1} - p_t + 1 > 2k;
тип , якщо блок коректний і в усьому масиві виконується R - L - 1 \ge 2k;
тип інакше.
Для кожного остачі по модулю будуємо префіксні суми по блоках цього класу, щоб швидко перевіряти, чи є на деякому відрізку блок типу або типу .
Відповідь на запит.
Знаходимо перший і останній нуль у [l,r]. Нехай їх індекси в масиві нулів дорівнюють та .
Якщо нулів немає — відповідь YES.
Якщо s-f+1 не ділиться на — відповідь NO.
Розглядаємо старти блоків f, f+k, f+2k, \dots.
Якщо серед них є блок типу — відповідь NO.
Якщо серед внутрішніх блоків (всіх крім першого та останнього) є блок типу — відповідь YES.
Інакше перевіряємо окремо перший і останній блок: чи можна зробити перший хід, використовуючи межу або межу . Якщо так — YES, інакше — NO.
Складність. Попередня обробка працює за , кожен запит обробляється за , отже загальна складність O(n+q).