Активація панелі#13043

Активація панелі (Розбір)

Розв'язання

Спочатку знайдемо відповідь без виконання операції.

Це просто максимальна довжина неперервного відрізка, що складається лише з одиниць.

Тепер розглянемо операцію в позиції $i$ .

Якщо $s_{i} = 0$ s_i=0, операцію можна виконати лише за умови

c_{i} \leq k .

c_i \le k.

Якщо $s_{i} = 1$ s_i=1, операцію можна виконати завжди.

Після вибору позиції $i$ не більше трьох позицій можуть стати рівними $1$ :

i, L_{i}, R_{i},

i,\ L_i,\ R_i,

де

L_{i} = max {j < i : s_{j} = 0, c_{j} < c_{i}},

L_i=\max\{j<i:s_j=0,\ c_j<c_i\},

а

R_{i} = min {j > i : s_{j} = 0, c_{j} < c_{i}} .

R_i=\min\{j>i:s_j=0,\ c_j<c_i\}.

Отже, спочатку потрібно знайти $L_{i}$ L_i та $R_{i}$ R_i для кожної позиції.

Пошук $L_{i}$ L_i

Стиснемо координати значень $c_{i}$ c_i.

Будемо обробляти позиції зліва направо та підтримувати дерево Фенвіка.

Для кожного стисненого значення дерево зберігатиме максимальний індекс позиції з нулем і таким значенням, яку ми вже обробили.

Для позиції $i$ робимо запит по всіх значеннях, строго менших за $c_{i}$ c_i.

Максимальний індекс серед них і буде рівним $L_{i}$ L_i.

Після цього, якщо $s_{i} = 0$ s_i=0, додаємо позицію $i$ у дерево Фенвіка.

Пошук $R_{i}$ R_i

Аналогічно обробляємо позиції справа наліво.

Тепер дерево Фенвіка зберігає мінімальний індекс.

Для кожної позиції $i$ запит по всіх значеннях, строго менших за $c_{i}$ c_i, дає $R_{i}$ R_i.

Таким чином, усі значення $L_{i}$ L_i та $R_{i}$ R_i можна знайти за

O (n lo g n) .

O(n\log n).

Відрізки навколо змінених позицій

Для кожної позиції $x$ визначимо $[l o_{x}, h i_{x}]$ [lo_x,hi_x] як максимальний відрізок одиниць, що містить $x$ , якщо змінити лише позицію $x$ на $1$ .

Якщо $s_{x} = 1$ s_x=1, це просто звичайний максимальний відрізок одиниць, який містить $x$ .

Якщо $s_{x} = 0$ s_x=0, розширюємося від $x$ через усі послідовні одиниці безпосередньо зліва та справа.

Усі ці значення можна знайти за $O (n)$ .

Тепер розглянемо операцію в позиції $i$ .

Візьмемо всі наявні позиції серед

i, L_{i}, R_{i} .

i,\ L_i,\ R_i.

Їх не більше трьох.

Відсортуємо їх:

x_{1} < x_{2} < \dots < x_{t} .

x_1 < x_2 < \dots < x_t.

Кожна позиція $x_{j}$ x_j спочатку відповідає відрізку

[l o_{x_{j}}, h i_{x_{j}}] .

[lo_{x_j},hi_{x_j}].

Дві сусідні змінені позиції $x_{j}$ x_j та $x_{j + 1}$ x_{j+1} потраплять в один фінальний відрізок одиниць тоді і тільки тоді, коли між ними немає незміненого нуля.

Нехай $p r e f_{i}$ pref_i — кількість нулів серед перших $i$ позицій.

Тоді між $x_{j}$ x_j та $x_{j + 1}$ x_{j+1} немає нуля рівно тоді, коли

p r e f_{x_{j + 1} - 1} - p r e f_{x_{j}} = 0.

pref_{x_{j+1}-1}-pref_{x_j}=0.

Якщо ця умова виконується, відповідні компоненти можна об'єднати.

Оскільки змінених позицій не більше трьох, кожну можливу операцію можна перевірити за $O (1)$ .

Доведення коректності

Операція може змінити лише позиції $i$ , $L_{i}$ L_i та $R_{i}$ R_i.

Тому кожен новий відрізок одиниць, який виникає після операції, повинен містити хоча б одну з цих позицій.

Для кожної зміненої позиції $x$ відрізок $[l o_{x}, h i_{x}]$ [lo_x,hi_x] містить рівно всі послідовні одиниці, які будуть з'єднані з $x$ , якщо змінити тільки її.

Два такі відрізки з'єднуються після операції рівно тоді, коли між відповідними зміненими позиціями немає незміненого нуля.

Префіксні суми кількості нулів перевіряють саме цю умову.

Отже, для кожної можливої операції ми коректно розглядаємо всі нові відрізки одиниць, які можуть виникнути.

Разом із варіантом, коли операція взагалі не виконується, це дає оптимальну відповідь.

Складність

Два проходи з деревом Фенвіка працюють за

O (n lo g n) .

O(n\log n).

Уся інша передобробка займає $O (n)$ , а кожна позиція перевіряється за $O (1)$ .

Отже, загальна складність становить

O (n lo g n)

O(n\log n)

за часом та

O (n)

за пам'яттю.

s_{i} = 0

c_{i} \leq k .

s_{i} = 1

i, L_{i}, R_{i},

L_{i} = max {j < i : s_{j} = 0, c_{j} < c_{i}},

R_{i} = min {j > i : s_{j} = 0, c_{j} < c_{i}} .

L_{i}

R_{i}

L_{i}

c_{i}

c_{i}

L_{i}

s_{i} = 0

R_{i}

c_{i}

R_{i}

L_{i}

R_{i}

O (n lo g n) .

[l o_{x}, h i_{x}]

s_{x} = 1

s_{x} = 0

i, L_{i}, R_{i} .

x_{1} < x_{2} < \dots < x_{t} .

x_{j}

[l o_{x_{j}}, h i_{x_{j}}] .

x_{j}

x_{j + 1}

p r e f_{i}

x_{j}

x_{j + 1}

p r e f_{x_{j + 1} - 1} - p r e f_{x_{j}} = 0.

L_{i}

R_{i}

[l o_{x}, h i_{x}]

O (n lo g n) .

O (n lo g n)