|
Скользящие окна
(Время: 2 сек. Память: 64 Мб Сложность: 73%)
Рассмотрим массив чисел b₁, ..., bₘ. Скользящими окнами длины k (k ≤ m) на этом массиве назовем все подотрезки длины k, то есть отрезки [b1, ..., bk], [b2, ..., bk+1], ..., [bm−k+1, ..., bm].
Дан массив чисел a₁, ..., aₙ длины n.
Необходимо ответить на q запросов следующего вида: для заданных l, r, k найти сумму минимумов на скользящих окнах длины k на подотрезке [aₗ, ..., aᵣ].
Входные данные
В первой строке входного файла INPUT.TXT даны два целых числа n и q (1 ≤ n, q ≤ 100 000) — длина массива и количество запросов.
Во второй строке даны n целых чисел a₁, ..., aₙ (1 ≤ aᵢ ≤ 10⁹) — значения чисел в массиве.
В следующих q строках даны запросы. В i-й из них даны три целых числа lᵢ, rᵢ и kᵢ (1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ r − l + 1).
Выходные данные
В выходной файл OUTPUT.TXT выведите q строк с ответами на запросы.
В i-й строке выведите единственное число – сумму минимумов на скользящих окнах длины kᵢ на подотрезке [aₗᵢ, ..., aᵣᵢ].
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6 3
4 6 1 2 5 3
2 5 2
2 4 1
1 6 6 | 4
9
1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
