Range Sum Query
Range Sum Query
Дан массив целых чисел, изначально заполненный нулями. С ним необходимо производить два типа операций:
- ! i x - присвоить ячейке i значение x;
- ? l r - узнать сумму значений на отрезке [l, r].
Входные данные
Первая строка содержит размер массива n и количество запросов m (1 ≤ n ≤ (109
+ 7), 1 ≤ m ≤ 2 * 105
). За ним следуют m запросов по одному в строке.
В процессе работы программы необходимо поддерживать два числа P и Q. Изначально P = 91, Q = 47.
Запрос вида "**! A B**" обозначает, что в ячейку (A + P) mod n необходимо записать число (B + Q) mod (109
+ 7).
Запрос вида "**? A B**" обозначает, что необходимо посчитать сумму между элементами (A + P) mod n, (B + Q) mod n включительно. Пусть ответ равен Z. Тогда необходимо изменить числа P и Q следующим образом:
P = (P * 31) + Z mod (109
+ 7),
Q = (Q * 29) + Z mod (109
+ 7).
Нумерация элементов начинается с нуля.
Все входные числа не превосходят 109
+ 7.
Выходные данные
Для каждого запроса на сумму нужно вывести ответ на него в отдельной строке.
10 8 ! 1 4 ! 2 5 ? 3 6 ! 4 1 ? 5 9 ! 1 4 ? 5 9 ? 5 9
52 1416 42558 103
15 6 ! 1 1 ! 5 2 ? 5 14 ! 8 7 ? 1 4 ? 4 13
97 0 0