Complexitate <tex>O(N + M)</tex>

Demonstratie: Vom considera sirul divizat in 'secvente de monotonie'. Doua secvente de monotonie consecutive sunt legate printr-un varf (care apartine amandurora). Fie V = numarul de varfuri si S = numarul de secvente de monotonie. Are loc relatia V = S-1.

*Demonstratie*: Vom considera sirul divizat in 'secvente de monotonie'. Doua secvente de monotonie consecutive sunt legate printr-un varf (care apartine amandurora). Fie V = numarul de varfuri si S = numarul de secvente de monotonie. Are loc relatia V = S-1.

* Consideram toate solutiile pentru care avem cel mult un element pe fiecare secventa de monotonie: atunci evident sol &le; S < V.
* Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu doua elemente. Daca alegem o secventa de monotonie pe care alegem doua elemente, pe restul secventelor este imposibil sa alegem doua si vom alege cel mult 1, atunci sol &le; S+1 = V

Atunci sol ≤ V oricare ar fi sol - lungimea unui sir alternant. Atunci V este valoarea maxima a lungimii unui subsir alternant.

O problema aparent simpla.. Dar stai.. Nu putem sa precalculam raspunsurile pentru ca nu avem destula memorie. Nu putem sa raspundem offline la query-uri pentru ca avem nevoie de raspunsul la query-ul anterior pentru a-l genera pe urmatorul. Ce este de facut ?
 

O problema aparent simpla.. Dar stati.. Nu putem sa precalculam raspunsurile pentru ca nu avem destula memorie. Nu putem sa raspundem offline la query-uri pentru ca avem nevoie de raspunsul de la ultimul query pentru a-l genera pe urmatorul. Ce este de facut ?
Avem foarte mult timp la dispozitie. Nu ne permitem ca pentru un query q sa pornim de la t=0 si sa urmam recurenta pana la t=q. Ce ne permitem in schimb este sa calculam la inceput valorile pana la pasul 10^7^ si sa retinem doar in anumite locuri rezultatul. Putem sa pornim cautarea atunci de la cel mai apropiat punct inainte de q. Vom retine evident rezultatul la puncte echidistante. Daca retinem rezultatul din <tex>{\sqrt{M}}</tex> in <tex>{\sqrt{M}}</tex> producem o balansare intre timp si memorie. Complexitatea finala va fi <tex>O(M + Q*{\sqrt{M}})</tex> ca timp si <tex>O({\sqrt{M}})</tex> ca memorie. Limita de memorie ne permite si mai mult. Cu cat gap-ul dintre punctele precalculate este mai mic, cu atat solutia va fi mai rapida.

==include(page="onis-2015/solutii-runda-1/semipal")==