Подотрезки с заданной суммой

Два указателя находят отрезок с суммой не больше $S$ за линию, но требуют неотрицательных чисел: только тогда сдвиг левой границы гарантированно уменьшает сумму.

Когда отрицательные числа есть, окно ломается. Работает другой приём.

Идея

Сумма на полуинтервале $(l, r]$ равна $P_r - P_l$. Значит, вопрос «сколько отрезков с суммой ровно $k$» — это вопрос «сколько пар префиксов отличаются ровно на $k$».

Идём слева направо, считаем префикс и держим словарь: сколько раз каждое значение префикса уже встречалось. Для текущего $P_r$ количество подходящих левых границ — это сколько раз встречалось $P_r - k$.

unordered_map<long long, long long> seen{{0, 1}};   // пустой префикс
long long prefix = 0, count = 0;
for (long long value : a) {
    prefix += value;
    auto it = seen.find(prefix - k);
    if (it != seen.end()) count += it->second;
    seen[prefix]++;
}

Проверено против квадратичного перебора: на тридцати тысячах случайных массивов с числами от $-5$ до $5$ и любыми $k$ — совпадение.

Две детали, без которых не работает.

{{0, 1}} в начале. Пустой префикс $P_0 = 0$ обязан быть в словаре, иначе потеряются все отрезки, начинающиеся с первого элемента.

Сначала считаем, потом добавляем. Если поменять строки местами, при $k = 0$ каждый префикс найдёт сам себя, и ответ вырастет на $n$.

Сумма, кратная k

Частая вариация: посчитать отрезки, сумма которых делится на $k$. Это то же самое, но сравниваются остатки префиксов, а не сами значения:

vector<long long> count(k, 0);
count[0] = 1;
long long prefix = 0, answer = 0;
for (long long value : a) {
    prefix = ((prefix + value) % k + k) % k;
    answer += count[prefix];
    count[prefix]++;
}

Словарь заменяется массивом длины $k$ — быстрее и проще. Двойная нормализация остатка обязательна: в C++ % от отрицательного числа даёт отрицательный результат, и индекс уйдёт за границу массива.

Тоже проверено перебором.

Тот же приём для XOR

Побитовое исключающее «или» обратимо само себе, поэтому «префиксный XOR» устроен точно так же: XOR на отрезке равен $X_r \oplus X_l$.

Отсюда количество подотрезков с заданным XOR считается тем же кодом, где + заменено на ^, а prefix - k — на prefix ^ k.

Частный случай — «сколько подотрезков имеют нулевой XOR»: это пары равных префиксов.

Самый длинный отрезок с заданной суммой

Если нужно не количество, а максимальная длина, в словаре хранят не счётчик, а самое раннее появление префикса:

unordered_map<long long, int> firstAt{{0, -1}};
long long prefix = 0;
int best = 0;
for (int i = 0; i < n; i++) {
    prefix += a[i];
    auto it = firstAt.find(prefix - k);
    if (it != firstAt.end()) best = max(best, i - it->second);
    if (!firstAt.count(prefix)) firstAt[prefix] = i;   // только первое!
}

Условие if (!firstAt.count(prefix)) принципиально: перезаписывая позицию, вы потеряете самое левое вхождение, а именно оно даёт максимальную длину.

Значение $-1$ для нулевого префикса — это «позиция перед началом массива», чтобы длина отрезка от начала считалась правильно.

Что выбрать

условие задачи	приём
все числа неотрицательны, сумма $\le S$	два указателя
все числа неотрицательны, сумма ровно $k$	два указателя тоже подойдут
есть отрицательные, сумма ровно $k$	префиксы и словарь
есть отрицательные, сумма $\le S$	сортировка префиксов или дерево Фенвика
сумма кратна $k$	префиксы по остаткам
максимальная сумма	Кадане

Обратите внимание на четвёртую строку: «сумма не больше $S$» при наличии отрицательных чисел — задача заметно сложнее, чем «сумма ровно $k$». Причина в том, что равенство ищется по хеш-таблице за константу, а неравенство требует упорядоченной структуры.

Про unordered_map

В таких решениях unordered_map — узкое место по времени, а иногда и источник провала: против стандартной хеш-функции существуют подобранные тесты, на которых все ключи попадают в одну корзину, и решение становится квадратичным.

Защита — примешать к ключу случайную константу или взять map (логарифм вместо константы, но без риска). На школьных олимпиадах атаки на хеш редки, на Codeforces — обычное дело.