Secvmax
Solutie 1
O sa sortam query-urile crescator. Cand parcurgem query-urile in ordinea sortarii unele pozitii din vectorul initial vor putea fi folosite (apar pe parcurs). Acum ne intereseaza sa tinem o structura care sa sa suporte adaugarea unei pozitii intr-un vector si sa ne zica cea mai lunga subsecventa "lipita". Pentru aceasta ori putem sa folosim o structura de date gen "paduri de multimi disjuncte" ori pentru fiecare capat al unei bucati "lipite" tinem celalat capat si de fiecare daca cand introducem o pozitie noua actualizam aceste informatii uitandu-ne la pozitia din stanga si cea din dreapta. Sa luam un exemplu:
Fie sirul initial 1, 2, 4, 2, 3 si query-urile 3, 1, 2, 4 care dupa sortare vor fi 1, 2, 3, 4. O sa parcurgem query-urile in ordinea sortarii. Se poate observa ca atunci cand ajungem la valoarea x a unui query toate valorile mai mici sau egale cu x din vectorul initial pot fi folosite. Trebuie sa gasim cea mai lunga bucata continua (lipita) de elemente mai mici sau egale cu x. Pe exemplu sirul va evolua asa (elementele cu valoarea 1 reprezinta numerele ce pot fi folosite):
----- 1, 2, 4, 2, 3
1 -> 1, 0, 0, 0, 0
2 -> 1, 1, 0, 1, 0
3 -> 1, 1, 0, 1, 1
4 -> 1, 1, 1, 1, 1.
Ca sa gasim cea mai lunga bucata de 1-uri lipite putem proceda in felul urmator: pentru fiecare bucata lipita deja aparuta de la pozitia x la pozitia y tinem doua valori: D[x] = y si L[y] = x (reprezentand capatul opus al bucatii). Lungimea unei astfel de bucati este y - x + 1. Trebuie sa mentinem aceste informatii in timp ce unele noi pozitii apar. Cand o noua pozitie x apare trebuie sa intializam informatia pentru segmentul x - x ( D[x] = x si L[x] = x ). Dupa aceea trebuie sa ne uitam la pozitiile x - 1 si x + 1. Avem doua bucati posibile care trebuiesc lipite cu noua pozitie (daca ambele exista o sa le lipim intre ele) : bucata L[x-1]...x-1 si x+1...D[x+1] ce pot fi unite cu x...x (stim ca aceste bucati exista daca avem o informatie in L[x-1] sau in D[x+1] ). Acum trebuie doar sa actualizam unele L-uri si unele D-uri. Ca sa mentinem cea mai lunga bucata lipita in primul rand trebuie sa observam ca aceasta poate doar sa creasca (doar lipim bucati). Asadar putem sa tinem o valoare lmax care sa o actualizam de fiecare data cand lipim niste bucati noi. Trebuie sa mai avem grija ca nu raspundem la intrebari in ordinea lor initiala ci in ordinea sortarii, de aceea trebuie sa tinem pentru fiecare intrebare pozitia initala pe care apare si sa raspundem la pozitia respectiva (putem tine raspunsurile intr-un vector si sa afisam abia la sfarsit).
Complexitatea acestor solutii (cea prezentata si cea care se foloseste de multimi disjuncte) este O(N log N + M log M) ambele luand punctajul maxim.
Solutie 2
Pentru fiecare element din sir vom calcula st[i] si dr[i] , adica lungimea maxima a unei secvente care se termina cu a[i] si contine doar elemente mai mici sau egale cu a[i], respectiv lungimea maxima a unei secvente care incepe cu a[i] si contine doar elemente mai mici sau egale cu a[i]. Aceste informatii le obtinem cu ajutorul unei stive a carei elemente se vor mentine sortate.
combinand st[i] si dr[i] obtine lungimea maxima a unei secvente care contine doar elemente mai mici sau egale cu a[i], vom nota aceasta valoare best[i]. Vom construi sirul sol[i] = max(best[j]), unde a[j] <= a[i]. Pentru fiecare intrebare vom cauta binar X cel mai mare numar mai mic sau egal cu Q, rapsunsul va fi sol[X]. Complexitatea acestei solutii este O(N log N + M log N).
Solutie oferita de 
