h1(#MinMaxStore). 'E. MinMaxStore':problema/MinMaxStore

?

Vom explica doar modul in care determinam daca pozitia de minim este corecta (pentru maxim modul de gandire este acelasi).
 
Parcurgem operatiile de la sfarsit spre inceput si mentinem un set S care la fiecare moment va contine pozitiile pe care minimul din permutare ar trebui sa se afle pentru ca la final acesta sa fie pe pozitia PMIN.
Mai formal, daca dupa operatia i (cu i de la M la 0), minimul se afla pe pozitia pos si pos ∈ S, atunci la final minimul se va afla pe pozitia PMIN.
Daca minimul se afla pe pozitia pos si pos ∉ S, atunci la final minimul nu se va afla pe pozitia PMIN.
 
Dupa operatia M, singura pozitie valida pentru minim este PMIN. Astfel S = {PMIN} initial.
 
Presupunem ca la acest moment stim cum arata S dupa operatia i si vrem sa aflam cum arata S dupa operatia i - 1. Fie (Ai, Bi) operatia STORE cu numarul i. Se disting 3 cazuri:
 
     a)   Ai ∈ S => S = S ∪ {Bi}     (daca minimul se afla in Bi, acesta va trece in Ai si cum Ai este in S, va ajunge la final pe PMIN).
 
 
     b)   Ai ∉ S, Bi ∈ S  => S = S \ {Bi}   (daca minimul se afla in Bi, acesta va trece in Ai si cum Ai nu este in S, acesta nu va mai ajunge la final pe PMIN)
 
     c)   Ai ∉ S, Bi ∉ S => S nu se modifica
 
La final (dupa operatia 0, adica inainte de orice operatie), daca S contine toate pozitiile din vector (de la 1 la N), atunci pozitia de minim e corecta. Altfel, nu.
 
Complexitatea per test va fi O(M * log(N)) daca se foloseste set, respectiv O(M) pentru unordered_set.

h1(#Pokemon3). 'F. Pokemon3':problema/Pokemon3