1. Идея

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

Классическая идея здесь — заменить каждый элемент на его вклад в баланс:

• если число чётное, считаем его как +1;
• если число нечётное, считаем его как -1.

Тогда для любого отрезка:

• сумма по этому отрезку равна 0, если
• количество +1 равно количеству -1, то есть
• число чётных равно числу нечётных.

Значит, задача сводится к подсчёту количества подотрезков с суммой 0.

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

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

Наблюдение 1

Пусть pref[i] — баланс на префиксе из первых i элементов:

• добавляем 1, если элемент чётный;
• вычитаем 1, если элемент нечётный.

Тогда сумма на отрезке [l..r] равна:

pref[r] - pref[l - 1]

Этот отрезок подходит тогда и только тогда, когда:

pref[r] = pref[l - 1]

То есть нужно найти количество пар одинаковых префиксных значений.

Наблюдение 2

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

Почему так?

Потому что каждый прошлый префикс с тем же значением задаёт один отрезок, у которого баланс равен нулю.

Наблюдение 3

Нужно не забыть про пустой префикс.

До начала массива баланс равен 0, и он уже встретился один раз. Поэтому в словарь сразу кладём:

cnt[0] = 1

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

3. Алгоритм

1. Считываем n и массив.
2. Создаём словарь cnt, где будем хранить, сколько раз встречался каждый префиксный баланс.
3. Инициализируем:
   • pref = 0 — текущий баланс,
   • ans = 0 — ответ,
   • cnt[0] = 1.
4. Идём по массиву слева направо:
   • если текущий элемент чётный, делаем pref += 1;
   • иначе делаем pref -= 1;
   • добавляем к ответу cnt[pref], потому что каждый прежний такой же префикс образует подходящий отрезок;
   • увеличиваем cnt[pref] на 1.
5. Выводим ans.

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

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

Рассмотрим массив, в котором каждый чётный элемент заменён на +1, а каждый нечётный — на -1.

Тогда для любого подотрезка сумма его элементов равна:

• число_чётных - число_нечётных.

Подотрезок подходит по условию тогда и только тогда, когда:

• число_чётных = число_нечётных,
• значит, сумма на этом подотрезке равна 0.

Теперь рассмотрим префиксные суммы pref.

Сумма на подотрезке [l..r] равна разности:

pref[r] - pref[l - 1].

Она равна 0 тогда и только тогда, когда:

pref[r] = pref[l - 1].

Значит, каждый подходящий подотрезок однозначно соответствует паре одинаковых префиксных сумм, и наоборот, каждая такая пара задаёт один подходящий подотрезок.

Алгоритм при обработке очередного значения pref добавляет к ответу количество его предыдущих появлений. Это ровно число подотрезков, оканчивающихся в текущей позиции и имеющих нулевой баланс.

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

5. Сложность

Каждый элемент массива обрабатывается один раз, каждая операция со словарём выполняется в среднем за O(1).

Итоговая сложность:

• время: O(n)
• память: O(n)

Это подходит для n до 2 * 10^5.

6. Код на C++17

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

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

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

    unordered_map<long long, long long> cnt;
    cnt.reserve(2 * n + 10);

    long long pref = 0;
    long long ans = 0;
    cnt[0] = 1;

    for (int i = 0; i < n; i++) {
        if (a[i] % 2 == 0) {
            pref += 1;
        } else {
            pref -= 1;
        }

        if (cnt.find(pref) != cnt.end()) {
            ans += cnt[pref];
        }
        cnt[pref]++;
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

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

cnt = {0: 1}
pref = 0
ans = 0

for x in a:
    if x % 2 == 0:
        pref += 1
    else:
        pref -= 1

    ans += cnt.get(pref, 0)
    cnt[pref] = cnt.get(pref, 0) + 1

print(ans)