Шабля ловить ворога , коли виконуються дві нерівності: 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 дорівнює
тобто максимум на префіксі й присвоєння в точці. Переходити зі станів із s \ge b_i сенсу немає: така шабля не додає покриття, а лише коштує грошей.
Обидві операції дає звичайне дерево відрізків із відкладеним додаванням і максимумом.
Наприкінці, коли шаблі скінчилися, звільняємо решту ворогів (їх ловлять шаблі з будь-якою достатньою гостротою) і виводимо максимум по всьому дереву. Нуль теж є допустимою відповіддю — можна не купувати нічого.
Складність — \mathcal{O}\bigl((n + m)\log(n+m)\bigr). Прибутки й вартості додаються, тому рахуйте у 64-бітному типі.