Решение олимпиадной задачи подсуммы

Навскидку - собрать все частичные суммы

a1  a1+a2  a1+a2+a3 ...

потом пробежаться по всем парам (i,j) массива частичных сумм - abs(S(j)-S(i)) будет соответствующей суммой подотрезка. Выбрать подходящие.

Частичная сумма есть в стандартной библиотеке :)

Решение за O(N log N).

Сразу пишу в псевдокоде. Операции на дереве работают за логарифм от его размера.

1. сделать суммы от 0 до текущего
2. загнать их в дерево
3. пройтись по этим суммам и используя дерево вычислить сколько из них меньше текущая минус M
4. вывести ответ

Вместо дерева (написанного руками) можно использовать например tree из G++

Чуть изменить чтобы хранить несколько одинаковых значений (например сведением к паре).

int main(){
int N, M;
cin >> N >> M;
vector<int> a;
a.push_back(0);
for (int i=0;i<N;i++){
    int x;
    cin >> x;
    a.push_back(x);
}
int p = 0;
int s = 0;
for (auto i : a){
    s+=i;
    H.insert(pii(s,p++));
}
int res = 0;
s = 0;
for (auto i : a){
    s += i;
    auto q = lower_bound(H.begin(), H.end(), pii(s - M,-1));
    res += H.order_of_key(*q);
}
cout << res<<endl;
}