1. Идея

В каждом запросе нужно найти сумму вида:

a_l * b_l + a_{l+1} * b_{l+1} + ... + a_r * b_r

Если считать её заново для каждого запроса, то один запрос может занимать до O(n) времени, а при q до 2 * 10^5 это слишком медленно.

Поэтому удобно заранее построить массив префиксных сумм для последовательности a_i * b_i.

Обозначим:

• c_i = a_i * b_i
• pref[i] — сумма первых i элементов массива c

Тогда сумма на отрезке [l, r] находится очень быстро:

pref[r] - pref[l - 1]

Это и есть основная идея решения.

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

1. В запросах всегда требуется сумма произведений элементов с одинаковыми индексами.
   Значит, можно сначала рассматривать не два массива a и b, а один массив c, где c_i = a_i * b_i.

2. После этого задача становится стандартной: нужно много раз находить сумму на отрезке массива.

3. Для таких задач почти всегда подходят префиксные суммы:

   • pref[0] = 0
   • pref[i] = pref[i - 1] + c_i

4. Тогда:

   • сумма на отрезке [1, r] равна pref[r]
   • сумма на отрезке [l, r] равна pref[r] - pref[l - 1]

5. Значения могут быть довольно большими:

   • a_i <= 10^4
   • b_i <= 10^4
   • значит, a_i * b_i <= 10^8
   • сумма по n = 2 * 10^5 элементам может достигать порядка 2 * 10^13

   Поэтому в C++ нужен тип long long.

3. Алгоритм

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

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

Пусть c_i = a_i * b_i.

Тогда по определению префиксной суммы:

• pref[r] = c_1 + c_2 + ... + c_r
• pref[l - 1] = c_1 + c_2 + ... + c_{l - 1}

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

c_l + c_{l+1} + ... + c_r

А это ровно:

a_l * b_l + a_{l+1} * b_{l+1} + ... + a_r * b_r

Значит, формула pref[r] - pref[l - 1] действительно даёт ответ на каждый запрос.

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;
    cin >> n >> q;

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

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i] * b[i];
    }

    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 = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

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

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