На доске записаны N цифр. Позиции, в которых записаны цифры, занумерованы целыми положительными числами от 1 до N. Далее M раз делаются запросы следующего вида: Выбираются два целых числа A и B (1 ≤ A ≤ B ≤ N) — параметры запроса. Вычисляется сумма всех

1 октября 2025
Информационные технологии

Условие:

На доске записаны N цифр. Позиции, в которых записаны цифры, занумерованы целыми положительными числами от 1 до N. Далее M раз делаются запросы следующего вида:

Выбираются два целых числа A и B (1 ≤ A ≤ B ≤ N) — параметры запроса.
Вычисляется сумма всех цифр на доске от A-й до B-й позиции включительно и записывается листе бумаги.
Все цифры от A-й до B-й включительно увеличиваются на 1 (при этом цифра 9' переходит в цифру 0'.
По заданой начальной последовательности цифр и параметрам всех запросов восстановите записи на листе бумаги.

Формат ввода
Первая строка входа содержит два целых числа N и M (1 ≤ N ≤ 2.5 ⋅ 105, 1 ≤ M ≤ 105). Вторая строка задаёт начальную последовательность цифр и состоит из N цифр. Первая цифра соответствует позиции 1, вторая — позиции 2... N-я — позиции N.

Каждая из последующих M строк содержит два целых числа A и B (1 ≤ A ≤ B ≤ N) — параметры соответствующего запроса.

Формат вывода
Выведите M строк — записанные на листе бумаги суммы в том порядке, в котором они были выписаны.

Пример 1
Ввод Вывод
4 3
1234
1 4
1 4
1 4
10
14
18
Пример 2
Ввод Вывод
4 4
1234
1 1
1 2
1 3
1 4
1
4
9
16
Пример 3
Ввод Вывод
7 5
9081337
1 3
3 7
1 3
3 7
1 3
17
23
1
19
5 на с++

Решение:

Для решения данной задачи мы можем использовать подход с использованием массива для хранения текущих значений цифр и дополнительного массива для хранения сумм. Давайте разберем решение по шагам.

Шаг 1: Чтение входных данных

Сначала мы считываем значения N и M, а затем считываем последовательность цифр.

Шаг 2: Инициализация массива

Создаем массив digits, который будет хранить текущие значения цифр, и массив sums, который будет хранить суммы для каждого запроса.

Шаг 3: Обработка запросов

Для каждого запроса мы:
1. Вычисляем сумму цифр от позиции A до B.
2. Записываем эту сумму в массив sums.
3. Увеличиваем каждую цифру от A до B на 1, при этом учитываем переход от 9 к 0.

Шаг 4: Вывод результатов

После обработки всех запросов выводим все суммы из массива sums.

Теперь давайте реализуем это на C++.

1. Мы используем для хранения цифр и результатов. 2. В цикле обрабатываем каждый запрос, сначала вычисляем сумму, затем обновляем цифры. 3. Сумма записывается в вектор , который затем выводится. - Данный алгоритм имеет временную сложность O(M * N) в худшем случае, что может быть неэффективно для больших значений N и M. Для оптимизации можно использовать подход с разностными массивами или сегментными деревьями, но это усложнит реализацию.