Банка фарб#13111

Банка фарб (Розбір)

Мазок лише копіює кольори праворуч. Тому в кожному досяжному розфарбуванні кожна дошка має джерело p(i) \le i, для якого b_i = c_{p(i)} (спочатку p(i) = i). Мазок (l, r) робить p(l), \ldots, p(r) рівними , і лишається неспадною: p(j) \le p(l) для j < l і p(j) \ge p(r) \ge p(l) для j > r.

Твердження. досяжне тоді й лише тоді, коли існує неспадна , для якої p(i) \le i і b_i = c_{p(i)} для всіх .

Необхідність показано вище. Навпаки, кожне використане джерело обслуговує відрізок [s_k, e_k], де k \le s_k. Зробимо мазки (k, e_k) для використаних джерел справа наліво. У цей момент дошка ще не змінена, бо попередні мазки починаються правіше від . Мазок фарбує також [k, s_k - 1], але ці дошки належать меншим джерелам і будуть перефарбовані пізніше, а всі наступні мазки закінчуються до s_k.

Кожне розфарбування рахуємо один раз. Розіб'ємо на максимальні блоки однакового кольору; блок починається з дошки s_j і має колір v_j. Якщо замінити всі джерела всередині блоку на найменше з них, лишиться коректною, тож блок може мати одне джерело k_j, де 1 = k_1 < k_2 < \ldots (сусідні блоки мають різні кольори) і k_j \le s_j. Виберемо джерела жадібно: k_j — перша дошка після k_{j-1} кольору v_j. За індукцією жадібне k_j ніколи не стоїть правіше за -те джерело будь-якої коректної , тож досяжне тоді й лише тоді, коли його жадібний ланцюжок існує і k_j \le s_j для всіх .

Нехай \mathrm{prv}_k — попередня дошка кольору c_k (, якщо такої немає). Жадібний ланцюжок може перейти від до k' тоді й лише тоді, коли \mathrm{prv}_{k'} < k < k'; це також виключає c_{k'} = c_k. Отже, досяжні розфарбування взаємно однозначно відповідають парам (жадібний ланцюжок, початки блоків 1 = s_1 < s_2 < \ldots) з k_j \le s_j.

Нехай f_i[k] — кількість таких префіксів довжини , останній блок яких має джерело . Тоді f_1[1] = 1 і для k' \le i+1

f_{i+1}[k'] = f_i[k'] + \sum_{k=\mathrm{prv}_{k'}+1}^{k'-1} f_i[k].

Перший доданок продовжує останній блок; сума починає новий блок з дошки i+1, що дозволено саме тому, що k' \le i+1. Відповідь — \sum_k f_n[k]. (Для попарно різних кольорів це число Каталана C_n.)

З префіксними сумами f_i кожен крок займає ; знаходимо сортуванням пар (c_i, i). Складність — O(n^2) за часом і за пам'яттю на тестовий випадок.