Индекс примечательности

Для начала рассмотрим случаи $$$P = 2$$$ и $$$P = 5$$$. Как известно, делимость на $$$2$$$ и $$$5$$$ зависит только от последней цифры числа. Соответственно, для ответа на запрос нужно посчитать подстроки $$$[i, j]$$$ ($$$l \le i \le j \le r$$$), последняя цифра которых $$$s_j$$$ делится на $$$P$$$. Пусть $$$p_1, p_2, \ldots, p_k$$$ ($$$l \le p_1 \le p_2 \le \ldots \le p_k \le r$$$) — это позиции в подстроке запроса, цифры на которых делятся на $$$P$$$. Тогда ответ на запрос равен $$$\sum \limits_{i=1}^k (p_i - l + 1) = (\sum \limits_{i=1}^k p_i) - k \cdot (l - 1)$$$. Чтобы найти число и сумму позиций с нужным свойством на подстроке, можно использовать два массива префиксных сумм.

Пусть теперь $$$P \ne 2$$$ и $$$P \ne 5$$$. Для каждого $$$i$$$ ($$$1 \le i \le |T|$$$) вычислим $$$a_i$$$ — значение числа $$$T_i T_{i+1} \ldots T_{|T|}$$$ по модулю $$$P$$$, положим также $$$a_{|T|+1} = 0$$$. Значения $$$a_i$$$ можно вычислить рекуррентно как $$$a_i = a_{i+1} + T_i \cdot 10^{|T| - i}$$$.

Тогда значение числа $$$T_i T_{i+1} \ldots T_j$$$ по модулю $$$P$$$ равно $$$(a_i - a_{j+1}) / 10^{|T| - j}$$$. Поскольку $$$10$$$ взаимнопросто с $$$P$$$ ($$$2$$$ и $$$5$$$ мы уже исключили из рассмотрения), подстрока $$$T_i T_{i+1} \ldots T_j$$$ делится на $$$P$$$ тогда и только тогда, когда $$$a_i = a_{j+1}$$$.

Таким образом, ответ на запрос $$$l, r$$$ равен числу пар $$$i, j$$$ ($$$l \le i < j \le r + 1$$$) таких, что $$$a_i = a_j$$$.

Для решения такой задачи можно воспользоваться так называемым алгоритмом Мо. Зафиксируем некоторое значение $$$K$$$ и отсортируем все запросы по возрастанию $$$\lfloor l / K \rfloor$$$, а при равенстве — по возрастанию $$$r$$$. Будем обрабатывать запросы в этом порядке и переходить к следующему запросу расширением/сужением отрезка предыдущего запроса. Будем хранить мультимножество $$$S$$$ значений $$$a_i$$$, находящихся в текущем отрезке. При расширении отрезка мы добавляем элемент в $$$S$$$, при сужении — удаляем. Также нужно параллельно с изменениями $$$S$$$ поддерживать число пар равных элементов в $$$S$$$. В качестве $$$S$$$ можно использовать либо хеш-таблицу, либо обычный массив (если заранее сжать значения $$$a_i$$$ в интервал $$$[0; |T|]$$$). Можно показать, что при выборе $$$K = \sqrt{|T|}$$$ число операций добавления и удаления элемента равно $$$O((|T| + q) \cdot \sqrt{|T|})$$$, что укладывается в ограничение по времени.