1. Идея

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

Перебирать все пары l, r нельзя: это заняло бы O(n^2), что слишком долго при n до 2 * 10^5.

Основная идея — использовать префиксные суммы и словарь, в котором хранится, сколько раз каждая префиксная сумма уже встречалась.

Если обозначить через pref[i] сумму первых i элементов, то сумма на отрезке от l до r равна:

pref[r] - pref[l - 1]

Нам нужно, чтобы она была равна S, то есть:

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

Отсюда:

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

Значит, когда мы находим текущую префиксную сумму pref, нужно узнать, сколько раз раньше встречалось значение pref - S. Каждое такое вхождение даёт один подходящий подотрезок.

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

Наблюдение 1

Сумма подотрезка удобно выражается через разность двух префиксных сумм.

Например, если массив такой:

a = [1, 2, 3, -1, 2]

Тогда префиксные суммы:

• до начала массива: 0
• после 1-го элемента: 1
• после 2-го: 3
• после 3-го: 6
• после 4-го: 5
• после 5-го: 7

Если взять подотрезок со 2-го по 4-й элемент, его сумма:

pref[4] - pref[1] = 5 - 1 = 4

Наблюдение 2

Для каждого конца отрезка можно быстро посчитать, сколько подходящих начал существует.

Пусть текущая префиксная сумма равна pref. Тогда нужны все предыдущие префиксные суммы, равные pref - S.

Если таких значений раньше встретилось k, то существует ровно k подотрезков, заканчивающихся в текущей позиции и имеющих сумму S.

Наблюдение 3

Нужно заранее считать, что префиксная сумма 0 встретилась один раз.

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

Поэтому в словарь сразу записываем:

cnt[0] = 1

3. Алгоритм

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

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

Докажем, что алгоритм считает количество всех и только тех подотрезков, сумма которых равна S.

Рассмотрим текущую позицию r. После обработки элемента a[r] текущая префиксная сумма равна:

pref = a[1] + a[2] + ... + a[r]

Подотрезок l..r имеет сумму S тогда и только тогда, когда:

a[l] + a[l+1] + ... + a[r] = S

Через префиксные суммы это равно:

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

Значит:

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

То есть для фиксированного r количество подходящих левых границ l равно количеству уже встреченных префиксных сумм со значением pref[r] - S.

Именно это число алгоритм прибавляет к ответу.

Почему мы не пропускаем подотрезки:

• каждый подотрезок имеет единственную правую границу r,
• когда алгоритм доходит до этой границы, соответствующая префиксная сумма pref[l - 1] уже находится в словаре,
• поэтому этот подотрезок будет учтён.

Почему не считаем лишнего:

• каждое добавление в ответ соответствует конкретной предыдущей префиксной сумме pref - S,
• а значит, конкретному подотрезку с суммой ровно S.

Следовательно, алгоритм корректен.

5. Сложность

Для каждого элемента массива выполняется константное число операций со словарём.

• Время: 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;
    long long S;
    cin >> n >> S;

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

    unordered_map<long long, long long> cnt;
    cnt[0] = 1;

    long long pref = 0;
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        pref += a[i];
        if (cnt.find(pref - S) != cnt.end()) {
            ans += cnt[pref - S];
        }
        cnt[pref]++;
    }

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

7. Код на Python 3

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

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

for x in a:
    pref += x
    ans += cnt.get(pref - S, 0)
    cnt[pref] = cnt.get(pref, 0) + 1

print(ans)