Observam ca politistii vor merge intai pe toate drumurile optime (dupa enunt) dintre nodurile legate direct sau indirect doar de muchii de categorie $1$, dupa aceea doar de muchii de categorie $<= 2$, de categorie $<= 3$, etc. Impartim muchiile dupa categorie. Consideram la fiecare pas $i$, $1 <= i <= D$, ca avem nodurile grupate in componente conexe astfel incat intre orice doua noduri din cadrul aceleasi componente conexe se poate ajunge mergand numai pe muchii de categorie strict mai mica decat $i$. Uitandu-ne la muchiile de categorie $i$, este posibil ca intre unele perechi de componente conexe sa fi "aparut" una sau mai multe muchii. Politistii vor dori sa faca drumuri de la orice componenta la orice alta folosind muchiile noi (atat cat se poate), avand grija sa aleaga de fiecare data un drum cu periculozitate maxima minima. Ne imaginam un graf, privind componentele deja stabilite ca pe noduri, si ca muchii intre ele doar muchiile originale de categorie $i$. Astfel, problema se reduce la a gasi un subset de muchii cu cost maxim minim astfel incat, dupa conectarea nodurilor lor aferente, intre orice doua noduri apartinand aceleeasi componente conexe din graful imaginat sa existe un drum - adica, un "Arbore partial de cost minim":http://www.infoarena.ro/problema/apm. Sortam, deci, muchiile din categoria curenta crescator dupa periculozitate si aplicam algoritmul lui Kruskal, avand grija sa introducem intr-un vector toate periculozitatile muchiilor selectate. Procedeul se repeta pana am epuizat toate muchiile. La final sortam descrescator vectorul pe care l-am mentinut si afisam primele $P$ elemente distincte.

Alternativ, mai simplu, putem pur si simplu sorta muchiile crescator dupa categorie, si in caz de egalitate crescator dupa periculozitate si, la sfarsit, sa aplicam Kruskal. Practic simulam procedeul de deasupra.

Alternativ, mai simplu, putem pur si simplu sorta muchiile crescator dupa categorie, si in caz de egalitate crescator dupa periculozitate si, la sfarsit, sa aplicam Kruskal. Practic simulam procesul de deasupra.

Complexitate timp: $O(MlogM + Mlog*N)$.
Complexitate spatiu: $O(N + M)$.
h1(#Pq). 'J. Pq':problema/pq

Observam ca o pozitie nu poate lua parte in mai mult de doua perechi - altfel, conform principiului cutiei ar exista fie la stanga, fie la dreapta, doua elemente "cele mai apropiate si egale", o absurditate. Urmarind acelasi fir logic, concluzionam ca o celula poate fi capatul stang al maxim unei perechi, si capatul drept al maxim unei perechi. Ne vine ideea de a retine in fiecare capat dreapta al vreunei perechi distanta dintre elementele perechii. Vom sorta queryurile crescator dupa $L$ si le vom rezolva interogand un arbore de intervale de maxim pe $(L ... R)$. De asemenea, trebuie avut grija ca, atunci cand capatul $L$ curent se misca la dreapta, toate perechile peste a caror capat stang am trecut sa fie scoase din arbore - suprascrise cu $0$. Parcurgem de la stanga la dreapta vectorul, retinand pentru fiecare valoare $lastOccurrence[i] = ultima pozitie pe care valoarea i a aparut$, initializat cu 0. Cand suntem pe o pozitie$i$ iar $lastOccurrence[v[i]] != 0$, inseamna ca s-a format o pereche cu $(lastOccurrence[v[i]]], i)$. Astfel, introducem in arborele de intervale valoarea $i - lastOccurrence[v[i]]$ pe pozitia $i$, si tinem minte ca atunci cand ajungem cu $L$ in dreptul pozitiei $lastOccurrence[v[i]] + 1$, vom seta pe $0$ pozitia $i$ din arborele de intervale. La final, in $lastOccurrence[v[i]]$ se pune valoarea $i$. Se parcurg queryurile si se raspunde la ele.
 
Complexitate timp: $O(NlogN)$.
Complexitate spatiu: $O(N)$.
 

h1(#Padure2). 'K. Padure2':problema/padure2