Nrsec

Primul pas in rezolvarea acestei probleme este sa vedem ca S poate fi cautat binar. Fie NR[S] numarul de subsecvente a caror suma este mai mica sau egala cu S. NR[S] este crescator in functie de S, cand creste S, creste si NR[S] deci S poate fi cautat binar. Ce ramane de facut este avand un S sa aflam NR[S]. Pentru ca numerele pot fi si negative sumele subsecventelor care se termina intr-un anumit punct nu sunt neaparat crescatoare, trebuie sa gasim o solutie care sa nu tina cont de asta.
O solutie este asa: facem sumele partiale A[i] = suma primelelor i numere din sir. Acum suma unei subsecvente i - j este A[j] - A[i - 1]. Sortam aceste sume tinand pentru fiecare si indicele ei. Parcurgem sumele sortate in ordine. Sa presupunem ca suntem la pozitia i. Vrem sa numaram cate subsecvente cu capatul in i au suma mai mica sau egala cu S. Fie j celalat capat al acestor subsecvente. J trebuie sa respecte A[j] - A[i - 1] ≤ S. Se poate usor observa ca j poate fi de la o anumita pozitie incolo in sirul sortat si daca i creste, j poate doar sa creasca. Explicatie: sa presupunem ca sirul de sume partiale este : -1, 1, 5, 6 si S = 2. Daca i = 1, j poate fi de la 1 spre sfarsit, daca i = 2, j poate fie de la 1 spre sfarsit, daca i = 3, j poate fi de la 3 spre sfarsit, daca i = 4, j poate fi de la 4 spre sfarsit. J poate fi astfel usor determinat in timp ce parcurgem vectorul cu i in O(N). Avand j pentru fiecare i putem deduce ca numarul subsecventelor care se au un capat in i si a caror suma este mai mica sau egala cu S este N - j + 1 (unde N este numarul elementelor din sir). Dar daca adunam toate aceste valori observam ca unele subsecvente le numaram de doua ori. Ca sa evitam acest lucru putem sa numaram doar pozitiile j care apar ca indice din vectorul initial (nesortat) inaintea lui i. Pentru aceasta putem folosi un arbore de intervale, sau un arbore indexat binar (orice structura care poate sa faca update si query pe un interval in O(log N)). La inceput in acesta tinem toate pozitiile posibile, si pe masura ce j creste scoatem pozitiile din spatele lui j. La pozitia i facem query pe intervalul 1...PI[i] (unde PI[i] este pozitia sumei partiale i inainte de sortare).
O alta solutie se bazeaza pe algoritmul merge sort si este asemanatoare cu modul de numarare a numarului de inversiuni dintr-o permutare. Va las pe voi sa va ganditi cum :).
Complexitatea acestor algoritmi in total este: O(N * log N * log S_MAX) (unde S_MAX este suma maxima a unei subsecvente)