Часом буває так#516

Часом буває так (Editorial)

Автор: Костянтин Денисов

Розробник: Андрій Холод

Розбір підготовано: Костянтин Денисов

Маємо бінарний масив 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).