1. Идея

Нужно много раз отвечать на вопрос: сколько чётных чисел находится на отрезке l..r.

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

Поэтому удобно заранее посчитать массив префиксных сумм:

• для каждой позиции хранить, сколько чётных чисел встретилось с начала массива до этой позиции.

Тогда ответ на любой запрос можно получить за O(1).

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

1. Для задачи важно не само значение числа, а только чётное оно или нет.

2. Каждое число можно заменить на индикатор:

   • 1, если число чётное;
   • 0, если число нечётное.

   Например, массив
   0 1 -1 2 -2
   превращается в
   1 0 0 1 1.

3. Если построить префиксную сумму pref, где pref[i] — количество чётных среди первых i элементов, то:

   • pref[r] — число чётных на префиксе 1..r;
   • pref[l - 1] — число чётных на префиксе 1..l-1.

   Тогда на отрезке l..r чётных будет: pref[r] - pref[l - 1].

4. Отрицательные числа тоже корректно проверяются на чётность. Например, -2 — чётное, -1 — нечётное.

3. Алгоритм

1. Считать n.
2. Считать массив из n чисел.
3. Построить массив pref длины n + 1:
   • pref[0] = 0;
   • для i от 1 до n:
     • если a[i - 1] чётное, прибавить 1;
     • иначе прибавить 0.
4. Считать q.
5. Для каждого запроса l, r вывести:
   • pref[r] - pref[l - 1].

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

Пусть pref[i] — количество чётных чисел среди первых i элементов массива.

Тогда:

• pref[r] считает все чётные на позициях от 1 до r;
• pref[l - 1] считает все чётные на позициях от 1 до l - 1.

Если из первого количества вычесть второе, то останутся только чётные числа на позициях от l до r.

То есть ответ на запрос равен: pref[r] - pref[l - 1].

Это верно для любого запроса, потому что префиксные суммы как раз позволяют выделять сумму или количество на любом подотрезке вычитанием двух префиксов.

5. Сложность

• Построение префиксного массива: O(n).
• Ответ на каждый запрос: O(1).
• Всего запросов q, значит общая сложность: O(n + q).
• Дополнительная память: O(n).

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> pref(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pref[i] = pref[i - 1] + (x % 2 == 0 ? 1 : 0);
    }

    int q;
    cin >> q;

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

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

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