Задача СумRMQтор (SUMRMQ)
Пояснения к тесту: Сгенерированная последовательность 2 19 8 17 30 31Полученная сумма 65=2+8+8+17+30
Заветной мечтой изобретателя Николя Барузова было изготовление машины (эремкьютера), основной функцией которой будет генерация последовательности случайных чисел. Последовательность генерируется следующим образом. Первое число последовательности равно X1, а каждое следующее вычисляется по формуле , где X1, A, B и q – заданные целые числа.Далее Николя задался следующей целью: расширить применимость эремкьютера путем ввода дополнительной функции – поиск минимального значения в сгенерированной последовательности. В процессе тестирования выяснилось, что эремкьютер-минимизатор находит минимум только из K последовательно расположенных элементов.Теперь Николя усовершенствует свою машину так, чтобы в заданной последовательности из N элементов находились минимумы для всех возможных числовых отрезков длиной K (отрезок составляют элементы, расположенные подряд), а затем вычислялась их сумма. Ваша задача написать программу, которая проверяет правильность работы машины путем подсчета указанной суммы.
Формат ввода/вывода:
Программа SUMRMQ считывает с клавиатуры шесть целых чисел, разделенных пробелом N, K, X1, A, B и q (3≤K≤N≤107, K≤106, 0≤A,B,X1≤109, 0≤q≤30). Программа должна вывести одно число – сумму минимумов на всех отрезках длины K.
Пример:
| Ввод | Вывод |
| 6 2 2 5 9 5 | 65 |