Сумма самых слабых партий

На заводе датчик качества каждую минуту пишет число — «прочность партии». Начальник смены смотрит на отчёт по окнам ровно из k подряд идущих минут и в каждом таком окне отмечает самую слабую (минимальную) партию.

Тебе нужно посчитать суммарную «слабость» смены: сумму минимумов по всем подряд идущим окнам длины k.

Важно: сумма может не помещаться в 32-битный тип (как на олимпиадах), ориентируйся на 64-битные целые.

Формат ввода:

• В первой строке два целых числа n и k (1 ≤ n ≤ 8000, 1 ≤ k ≤ 8000, k ≤ n).
• Во второй строке n целых чисел a1, a2, ..., an (−10^6 ≤ ai ≤ 10^6).

Формат вывода:

• Выведи одно целое число — сумму минимумов по всем окнам длины k.

Ограничения:

• 1 ≤ n ≤ 200000
• 1 ≤ k ≤ n
• −10^6 ≤ ai ≤ 10^6

Пример: Ввод:

5 3
4 2 5 1 3

Вывод:

4

Перебирать минимум каждого окна отдельно слишком долго: при n до 200000 вариант с просмотром k элементов в каждом окне может занять O(n·k). Нужно не искать минимум заново, а переносить полезную информацию из предыдущего окна.

Используем монотонную очередь — deque, где лежат индексы элементов. Значения по этим индексам идут по возрастанию, поэтому в начале очереди всегда находится минимум текущего окна.

Почему можно удалять элементы с конца? Когда приходит a[i], любой элемент a[j] >= a[i] справа уже не сможет стать минимумом: новый элемент не больше него и останется в окнах дольше, ведь его индекс больше. Такие элементы больше не нужны.

План:

• Создать пустую deque и переменную для ответа.
• Идти по массиву слева направо, для каждого индекса i.
• Пока в конце deque есть индекс j с a[j] >= a[i], удалить его с конца.
• Добавить i в конец deque.
• Левая граница текущего окна длины k равна i - k + 1. Удалить из начала все индексы, которые меньше этой границы: они уже вышли из окна.
• Когда i >= k - 1, первое полное окно уже построено. Добавить к ответу a[dq[0]].

Очередь хранит индексы, а не сами значения: так легко проверить, не вышел ли элемент за левую границу окна. Каждый индекс добавляется один раз и удаляется не более одного раза, поэтому общее время O(n), а памяти нужно O(k).

Частая ошибка — не удалять «просроченные» индексы из начала очереди. Тогда минимум может относиться к элементу, которого в текущем окне уже нет. Ответ лучше накапливать в 64-битном целом: сумма минимумов может быть большой по модулю.