Mountains#522

Mountains (Editorial)

Розіб'ємо задачу на дві частини: допоміжну «локальну» і загальну.

Локальна задача. Нехай є число , і треба зробити a \mid x \ge b, витративши якнайменше монет (тобто мінімізувавши ). Позначимо цю мінімальну вартість F(a, b).

Якщо a \ge b, то x = 0. Інакше побудуємо жадібно по бітах. Спершу знайдемо найменший рівень , для якого встановлення усіх бітів нижче вже не рятує, тобто a \mathbin{|} (2^i - 1) < b: це означає, що доведеться чіпати біт . Візьмемо маску з усіх бітів до включно, а далі йдемо від старшого біта до молодшого і прибираємо з маски черговий біт, якщо після цього нерівність a \mathbin{|} x \ge b ще виконується. Отримана маска і є мінімальним : кожен біт ми знімали за першої ж нагоди, починаючи зі старших, а старший біт «важить» більше за всі молодші разом.

Загальна задача. Гора — це неспадний префікс і незростаючий суфікс. Тому порахуємо дві допоміжні величини:

  • — мінімальна вартість зробити перші елементів неспадними, і — значення -го елемента після цього;

  • — те саме для суфікса , який має бути незростаючим (тобто неспадним, якщо читати справа наліво).

Обидві рахуються жадібно одним проходом: \mathrm{prm}[i+1] = a_i \mathbin{|} F(a_i, \mathrm{prm}[i]), а до вартості додаємо F(a_i, \mathrm{prm}[i]). Жадібність тут коректна, бо ми робимо кожен елемент якомога меншим за умови «не менший за попередній», а менше значення ніколи не ускладнює життя наступним.

Нарешті, переберемо місце «стику»: для кожного від до відповідь-кандидат дорівнює \mathrm{pr}[i] + \mathrm{sf}[i]. Тут перші елементів утворюють неспадну частину, а решта — незростаючу; хоч би як співвідносились значення на стику, така послідовність уже є горою (вершина опиниться або в , або в i+1).

Відповідь — мінімум по всіх . Складність — \mathcal{O}(n \log A) на тест, де \log A \approx 30.