Вороги та шаблі#204

Вороги та шаблі (Розбір)

Шабля ловить ворога , коли виконуються дві нерівності: a_i \ge c_j і b_i \ge d_j. Прибуток — це сума винагород за спійманих ворогів мінус вартість куплених шабель, і кожного ворога зараховуємо щонайбільше раз.

Ключове спрощення: ворога ловить хоч якась із куплених шабель. Тому важливий не весь набір шабель, а лише те, які пари «довжина–гострота» він покриває. Це підказує замітання за однією координатою.

Замітання за довжиною. Відсортуємо шаблі за спаданням a_i, а ворогів — за спаданням c_j, і оброблятимемо шаблі по черзі. Коли ми доходимо до шаблі з довжиною , усі вороги з c_j > a вже ніколи не будуть спіймані наступними шаблями (вони коротші). Отже, саме в цей момент їхню долю можна остаточно вирішити: такого ворога спіймано тоді й лише тоді, коли серед уже куплених шабель є хоч одна з гостротою \ge d_j.

А оскільки всі вже оброблені шаблі мають довжину не меншу за c_j, умова зводиться до однієї величини — максимальної гостроти серед куплених шабель.

Динаміка. Заведемо стан «максимальна гострота серед куплених шабель дорівнює » і зберігатимемо для нього найкращий поточний прибуток. Значення стиснемо координатно (беремо всі b_i та d_j). Спочатку допустимий лише стан «шабель немає» зі значенням .

Тепер потрібні дві операції:

  • звільнення ворога : додати його винагороду до всіх станів із s \ge d_j — це додавання на відрізку;

  • купівля шаблі : нове значення стану b_i дорівнює

    \max_{s < b_i} (\text{значення стану } s) \;-\; \mathit{cost}_i,

    тобто максимум на префіксі й присвоєння в точці. Переходити зі станів із s \ge b_i сенсу немає: така шабля не додає покриття, а лише коштує грошей.

Обидві операції дає звичайне дерево відрізків із відкладеним додаванням і максимумом.

Наприкінці, коли шаблі скінчилися, звільняємо решту ворогів (їх ловлять шаблі з будь-якою достатньою гостротою) і виводимо максимум по всьому дереву. Нуль теж є допустимою відповіддю — можна не купувати нічого.

Складність — \mathcal{O}\bigl((n + m)\log(n+m)\bigr). Прибутки й вартості додаються, тому рахуйте у 64-бітному типі.