1. Идея

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

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

Поэтому надо заранее подготовить информацию, которая позволит отвечать на каждый запрос за O(1).

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

• если a[i] чётное, считаем его как 1,
• если нечётное, считаем как 0.

Тогда cnt[i] будет означать количество чётных чисел среди первых i элементов.

После этого ответ на запрос [l, r] находится как:

cnt[r] - cnt[l - 1]

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

1. Нас интересует не само значение элемента, а только факт, чётный он или нет.

2. Для каждого элемента можно мысленно заменить:

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

   Тогда задача превращается в поиск суммы на отрезке.

3. Если известны префиксные суммы:

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

   то на отрезке [l, r] остаётся только разность этих двух значений.

4. Отрицательные числа тоже могут быть чётными. Например, -2 — чётное. Проверка a[i] % 2 == 0 корректно это определяет.

3. Алгоритм

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

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

Докажем корректность.

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

Тогда:

• cnt[r] считает все чётные элементы на позициях от 1 до r,
• cnt[l - 1] считает все чётные элементы на позициях от 1 до l - 1.

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

Значит, количество чётных чисел на отрезке [l, r] равно cnt[r] - cnt[l - 1].

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

5. Сложность

Построение массива cnt:

• O(n)

Обработка всех запросов:

• O(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> a(n + 1);
    vector<int> cnt(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[i] = cnt[i - 1] + (a[i] % 2 == 0 ? 1 : 0);
    }

    int q;
    cin >> q;

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

    return 0;
}

7. Код на Python 3

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

cnt = [0] * (n + 1)
for i in range(1, n + 1):
    cnt[i] = cnt[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(cnt[r] - cnt[l - 1])