Разбор задачи «Сумма элементов, кратных D, на отрезке»

1. Идея

Для каждого запроса нужно найти сумму элементов массива на отрезке [l, r], которые делятся на D.

Если отвечать на каждый запрос напрямую, перебирая все элементы от l до r, то в худшем случае получится слишком долго: до n * q, а это при n, q до 2 * 10^5 уже не проходит.

Поэтому нужно подготовить массив так, чтобы каждый запрос обрабатывался очень быстро. Для этого удобно использовать префиксные суммы.

2. Наблюдения

Пусть мы построим новый массив:

• если a[i] кратно D, то оставляем его как есть;
• иначе заменяем на 0.

Тогда задача сводится к обычной задаче: найти сумму элементов на отрезке.

Например, если:

• a = [1, 3, 6, 7, 9]
• D = 3

то новый массив будет:

• [0, 3, 6, 0, 9]

Теперь сумма подходящих элементов на отрезке [l, r] — это просто сумма этого нового массива на отрезке.

Для быстрого нахождения суммы на любом отрезке строим массив префиксных сумм pref, где:

• pref[i] — сумма подходящих элементов среди первых i чисел.

Тогда ответ на запрос [l, r] равен:

• pref[r] - pref[l - 1]

3. Алгоритм

1. Считываем n, q, D.
2. Создаём массив префиксных сумм pref длины n + 1.
3. Идём по массиву слева направо:
   • pref[i] = pref[i - 1]
   • если текущий элемент a[i] делится на D, прибавляем его к pref[i]
4. Для каждого запроса (l, r) выводим:
   • pref[r] - pref[l - 1]

4. Почему это работает

Рассмотрим, что хранится в pref[i].

Это сумма всех элементов среди первых i, которые кратны D.

Тогда:

• pref[r] — сумма всех подходящих элементов на префиксе от 1 до r
• pref[l - 1] — сумма всех подходящих элементов на префиксе от 1 до l - 1

Если из первой суммы вычесть вторую, останутся только элементы с позиций от l до r.

То есть:

• pref[r] - pref[l - 1] — это ровно сумма элементов на отрезке [l, r], кратных D

Значит, алгоритм даёт правильный ответ на каждый запрос.

5. Сложность

Построение префиксного массива:

• O(n)

Обработка каждого запроса:

• O(1)

Общая сложность:

• O(n + q)

Память:

• O(n)

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, q;
    long long D;
    cin >> n >> q >> D;

    vector<long long> pref(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pref[i] = pref[i - 1];
        if (x % D == 0) {
            pref[i] += x;
        }
    }

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << pref[r] - pref[l - 1] << '\n';
    }

    return 0;
}

7. Код на Python 3

n, q, D = map(int, input().split())
a = list(map(int, input().split()))

pref = [0] * (n + 1)
for i in range(1, n + 1):
    pref[i] = pref[i - 1]
    if a[i - 1] % D == 0:
        pref[i] += a[i - 1]

for _ in range(q):
    l, r = map(int, input().split())
    print(pref[r] - pref[l - 1])