Задача C. Кратные суммы ≡

Условие

У Анжелики есть массив натуральных чисел a, длина которого равна n, а также у Анжелики есть любимое число, равное s. Жене очень нравится этот массив, поэтому он просит Анжелику проводить над данным массивом операции. Всего Женя попросит Анжелику выполнить q операций. Каждая операция имеет один из двух видов:

• 1 k d — Женя просит Анжелику присвоить k-му элементу массива значение d (то есть, a_k = d);
• 2 — Женя просит Анжелику сообщить количество пар чисел l и r таких, что 1 ≤ l ≤ r ≤ n и сумма a_l + a_l + 1 + ...  + a_r − 1 + a_r кратна s.

Так как Женя очень надоедливый и хочет спросить Анжелику очень много раз, Анжелика скинула эту работу на Вас! Помогите Анжелике!

Формат входных данных

В первой строке вводятся натуральные числа n, s и q — длина массива, любимое число Анжелики и количество операций соответственно (1 ≤ n, q ≤ 50000, 2 ≤ s ≤ 50). В следующей строке вводится массив Анжелики (1 ≤ a_i ≤ 10⁹).

В последующих q строках вводятся запросы Жени. Если первое число в строке равно 1, то после него следуют числа k и d, это означает, что Женя хочет изменить значение a_k на d. Если первое число в строке равно 2, то после него ничего не следует, это означает, что Женя хочет узнать количество пар чисел l и r таких, что 1 ≤ l ≤ r ≤ n и сумма a_l + a_l + 1 + ...  + a_r − 1 + a_r кратна s.

Гарантируется, что существует хотя бы один запрос второго вида, а также гарантируется, что в любой момент любое число из массива Анжелики является натуральным числом, не большим 10⁹.

Формат выходных данных

Для каждого запроса второго вида на отдельной строке выведите количество подходящих пар чисел l и r.

Примеры тестов

4 3 5
1 2 1 2
2
1 2 1
2
1 2 3
2

4
2
3

Разбор

По условию задачи понятно, что задача на дерево отрезков. Самое проблемное в дереве отрезков — придумать способ объединения ответа для двух отрезков.

Для начала определимся, что мы будем хранить в вершине. Авторы предлагают хранить ответ для данной вершины, остаток по модулю s суммы всех чисел в нем, количество префиксов с некоторыми остатками, количество суффиксов с некоторыми остатками. Чтобы получить остаток от деления на s новой вершины, нужно сложить остатки от деления двух отрезков по модулю s. Чтобы объединить префиксы, нужно взять массив префиксов левого куска и, соблюдая остатки, прибавить к нему массив префиксов правого куска. Аналогично с суффиксами. Теперь, чтобы найти отрезки, которые начинаются в правом куске, а заканчиваются в левом, нужно брать суффиксы левого куска и префиксы правого и объединять их согласно остаткам.

Несложно заметить, что задача базовая и не требовала особых усилий.