Велепин и маркетинг

Давайте отсортируем людей по их требованию размера группы. Предположим у нас есть такой человек $$$i$$$, что он не доволен, и есть человек $$$j > i$$$, который доволен. Тогда мы можем заменить $$$j$$$ человека в его группе на $$$i$$$ и ответ для нас не ухудшится. Отсюда следует, что для конкретного $$$k$$$ ответ это какой-то префикс людей, которых мы можем сделать довольными. Давайте также докажем, что существует такая расстановка групп, которая покрывает тот же самый префикс, и каждая группа это непрерывный отрезок. Давайте возьмем какое-нибудь корректное разбиение по группам. Тогда каждая группа будет представлять из себя набор несвязных отрезков. Давайте возьмем самый левый из таких отрезков. Заметим, что мы можем его про swap'ать до ближайшего отрезка такой же группы справа, при чем ничего не сломав. Таким образом мы получили, что мы можем искать решение в виде разбиения каждого префикса на валидные группы, которые являются отрезками. Будем решать эту задачу с помощью динамического программирования.

Пусть $$$dp[i]$$$ – максимальное количество групп, на которые можно разбить $$$i$$$-й префикс, так чтобы все были довольны (при чем нельзя использовать элементы за префиксом). База динамики: $$$dp[0] = 0$$$ (пустой префикс максимум можно разбить на 0 групп). Переход: для $$$i$$$-го человека его группа должна иметь размер хотя бы $$$a[i]$$$, поэтому переход выглядит следующим образом $$$dp[i] = \underset{0 \leqslant j \leqslant i - a[i]}{\max} dp[j] + 1$$$. Но что если $$$a[i] > i$$$? Тогда мы не можем набрать $$$i$$$-й префикс. Тогда положим $$$dp[i] = -\infty$$$. Эту динамику можно посчитать с помощью префиксных максимумов. Эта часть решения работает за $$$\O(n)$$$. Ранее мы сказали, что ответом будет являться какой-то префикс людей, которые будут довольны. Если мы можем разбить префикс на какое-то количество групп, то этот ответ может являтся префиксом для всех $$$k \leqslant dp[i] + n - i$$$. (мы разбиваем наш префикс соотвественно $$$dp$$$, а остальных людей расскидываем по одному в группу) Если мы не можем сделать весь префикс довольным ($$$dp[i] = -\infty$$$), то нам надо докидывать людей извне. Таким образом максимальное количество групп, на которые мы можем разбить, если $$$i$$$-й префикс полностью доволен, это $$$n - a[i] + 1$$$. Заметим, что если каким-то префиксом мы можем набрать $$$k$$$, то тогда можем набрать и $$$k - 1$$$ (объединив две группы в одну). Тогда нам нужно найти самый большой префикс, который подходит для данного $$$k$$$ в запросе. Это можно сделать массивом суффиксных максимумом за $$$O(q)$$$ суммарно. Итоговая асимптотика решения: $$$\O(n \log n + q)$$$.