В задаче требуется найти количество подотрезков массива, сумма на которых не равна $$$K$$$. Будем для простоты считать $$$X$$$ — количество подотрезков с суммой, равной $$$K$$$. Тогда ответ — это $$$\texttt{количество вообще всех подотрезков} - X = \frac{n \cdot (n + 1)}{2} - X$$$.

Решение 1:

Нередко в задачах на поиск количества подотрезков, удовлетворяющих некоторому условию, можно применить такую идею: переберём правую границу $$$r$$$ и для каждой правой границы быстро узнаем количество подходящих левых.

Давайте заранее насчитаем $$$pref_i$$$ — массив префиксных сумм. Дальше перебираем правую границу искомого подотрезка в порядке возрастания. Нужно узнать количество таких $$$l$$$, что $$$pref_r - pref_{l - 1} = k$$$, то есть $$$pref_{l - 1} = pref_r - k$$$. Можно хранить все уже рассмотренные $$$pref_i$$$ в словаре $$$d$$$. Тогда количество подходящих $$$l$$$ равно $$$d[pref_r - k]$$$, так как $$$l - 1 \in [0, r - 1]$$$.

Сложность работы: $$$\mathcal{O}(n) / \mathcal{O}(n\log n)$$$ в зависимости от сложности работы словаря.

Решение 2:

Решим более простую задачу, когда в массиве не может быть нулей. Введём обозначение $$$sum(l, r) = \sum\limits_{i = l}^r a_i$$$.

Пусть для некоторой левой границы $$$l_1$$$ существует некоторая правая граница $$$r_1$$$, что $$$sum(l_1, r_1) = k$$$. Заметим, что таких $$$r_1$$$ для фиксированной $$$l_1$$$ не более одной штуки, так как для всех $$$r' < r_1$$$ $$$sum(l_1, r') < sum(l_1, r_1) = k$$$, а для всех $$$r' > r_1$$$ $$$sum(l_1, r') > sum(l_1, r_1) = k$$$ (это следует из того, что в массиве все числа положительные).

Теперь возьмём $$$l_2 = l_1 + 1$$$, тогда, если и существует такое $$$r_2$$$, что $$$sum(l_2, r_2) = k$$$, то обязательно $$$r_2 > r_1$$$, так как $$$sum(l_2, r_1) < k$$$, ведь $$$a_{l_1} > 0$$$.

То есть если перебирать левую границу и двигать $$$l$$$ от $$$1$$$ до $$$n$$$, то потенциальная правая граница подходящего подотрезка будет двигаться только вправо. Значит, можно честно перебирать левую границу, затем двигать правую, пока $$$sum(l, r) < k$$$. Если сумма всё-таки равна $$$k$$$, значит, отрезок $$$[l, r]$$$ подходит.

Более простую задачу научились решать, вернёмся к исходной.

Аналогичным образом найдём для каждой левой границы минимальную правую $$$r_1$$$, что для всех $$$r \ge r_1$$$ $$$sum(l, r) \ge k$$$, и минимальную $$$r_2$$$, что для всех $$$r \ge r_2$$$ $$$sum(l, r) > k$$$. Тогда для фиксированной $$$l$$$ все подходящие правые границы лежат на $$$[r_1, r_2)$$$.

Сложность работы: $$$\mathcal{O}(n)$$$.