Щасливі з піцою#12985

Щасливі з піцою (Розбір)

Позначимо dp_i — максимальну кількість «щасливих» днів, якщо враховано лише перші i піц.

Щоб оновити dp_i, потрібно визначити, скільки піц можна з’їсти в останній день. Нехай останній день охоплює підпослідовність (j + 1, \dots, i). Вона має бути «щасливою», тобто жоден тип піци не зустрічається рівно один раз. Тоді dp_i = \max (dp_i, dp_j + 1).

Щоб швидко перевіряти, чи підпослідовність (j + 1, \dots, i) є «щасливою», підтримуємо для кожного типу піци позиції її появ. Для кожного типу між двома останніми появами збільшимо лічильник «поганих» позицій cnt_j на 1 — це означає, що в цьому діапазоні тип зустрічається рівно один раз.

Таким чином, серед усіх позицій , де xnt_j = 0 (тобто підпослідовність до утворює щасливий день), обираємо ту, що дає найбільше dp_j.

Для ефективної реалізації обчислення максимуму серед позицій із cnt_j = 0 можна використовувати дерево відрізків або іншу структуру даних із можливістю оновлень cnt_j на відрізку і пошуку максимуму серед пар (-cnt_j, dp_j).