Комбо-удары на сумму K

В игре есть полоса комбо из N ударов подряд. За i‑й удар дают a_i очков (может быть и штраф — отрицательное число). Игрок выбирает один непрерывный отрезок ударов и получает сумму очков на этом отрезке.

Тренер записал целевое число K и хочет знать: сколько разных непрерывных отрезков дают ровно K очков.

Нужно посчитать количество пар (l, r), где 1 ≤ l ≤ r ≤ N и a_l + a_{l+1} + ... + a_r = K.

Формат ввода

Первая строка: два целых числа N и K. Вторая строка: N целых чисел a_1, a_2, ..., a_N.

Формат вывода

Выведите одно целое число — количество непрерывных отрезков с суммой K.

Ограничения

• 2 ≤ N ≤ 35000
• -100000 ≤ a_i ≤ 100000
• -1000000000 ≤ K ≤ 1000000000

Пример

Ввод:

5 3
1 2 1 -1 2

Вывод:

3

Пояснение: подходят отрезки [1..2], [2..4], [3..5].

Ключевое наблюдение: сумма на отрезке [l..r] равна s[r] - s[l-1], где s[i] — префиксная сумма первых i элементов (s[0]=0). Тогда условие a[l]+...+a[r]=K превращается в s[l-1] = s[r] - K.

Значит, для каждого правого конца r достаточно знать, сколько раз раньше встречалась префиксная сумма s[r]-K. Это удобно считать на лету словарём (hash map): ключ — значение префиксной суммы, значение — сколько раз оно уже было.

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

План:

• Заведи s = 0 и словарь cnt, где cnt[0]=1 (пустой префикс).
• Иди по массиву:
• обнови s += a[i].
• добавь к ответу cnt[s - K] (если ключа нет — 0), например: ans += cnt.get(s - K, 0).
• увеличь cnt[s] на 1.
• Выведи ans.

Сложность: O(N) по времени и O(N) по памяти (в худшем случае все префиксные суммы разные).

Частая ошибка: забыть cnt[0]=1 или перепутать порядок обновлений (сначала считать вклад в ответ, потом увеличивать cnt[s]), иначе отрезки, начинающиеся с 1, и/или нулевой длины будут учтены неверно.