Revizia anterioară Revizia următoare
Solutia problemei Veverite
Subtaskul 1: N,Q ≤ 2000
O soluţie greedy uşor de intuit ar fi ca pentru fiecare query să parcurgem şirul de la stânga la dreapta şi să menţinem un set cu elementele pe care nu le-am adăugat încă la suma totală. În momentul când întâlnim un "blocaj" (adică suma este mai mică strict decât valoarea de la pasul curent) extragem din setul de elemente maximul până când se respectă restricţia din nou. După ce am rezolvat blocajul îl adaugăm şi pe el în set şi trecem mai departe.
Deoarece elemente din vector sunt în ordine crescătoare, extragerea elementului maxim şi adăugarile pot fi simulate uşor cu ajutorul unei stive.
Complexitate: O(N * Q)
Subtaskul 2: Ai ≤ 100, pentru 1 ≤ i ≤ N, N,Q ≤ 105
Se observă că pentru query-urile mai mari decât 100, răspunsul va fi clar 0. Putem precalcula răspunsul pentru fiecare valoare iniţială posibilă de la 1 la 100 folosind soluţia anterioară şi să răspundem la query-uri în O(1).
Complexitate: O(N * valmax + Q)
Subtaskul 3: 1 ≤ N, Q ≤ 105, 1 ≤ Ai ≤ 109
Observaţie: Pentru un vector există maxim 2 * log(valmax) blocaje.
Demonstraţie: Pentru oricare 3 elemente adiacente din şirul de elemente pe care le vom considera "blocaje" se împlineşte următoarea inegalitate:
a * 2 < c (unde a, b şi c sunt cele 3 elemente), deoarece la pasul în care ne-am blocat în b am adăugat cel puţin un element mai mare sau egal decât a la sumă (întrucât şi a se afla la acel moment în set). Astfel, la fiecare 2 elemente suma se dublează, ceea ce înseamnă că în 2 * log(valmax) paşi îşi va atinge valoarea maximă. Dacă menţinem setul necesar în greedy ca o listă de intervale de valori nefolosite putem procesa mult mai rapid şirul. Căutam binar poziţia primului blocaj şi adaugăm în listă intervalul de elemente până la acel blocaj. Pentru a simula procesul de extragere de maxim din set de un număr repetat de ori, verificăm dacă trebuie să adaugăm complet ultimul interval din listă. Dacă da, atunci îl adaugăm şi trecem mai departe, altfel căutam binar cât este necesar să adaugăm din el. Apoi căutam binar poziţia următorului blocaj şi tot aşa mai departe până am procesat tot.
Complexitate finală: O(N * log(valmax) * log(N))
