Un _greedy_ care ar rezolva corect fiecare query in parte ar fi urmatorul: Cat timp mai exista copii in interval, se alege cel a carui stramutare ar fi cat mai putin costisitoare si se muta. Astfel, fie cel mai din stanga copil din interval se va muta pe cel mai apropiat scaun liber din stanga din afara intervalului, fie cel mai din dreapta copil se va muta pe cel mai apropiat scaun liber din dreapta din afara intervalului. Pentru a calcula costul obtinut de acest algoritm, este suficient sa se mentina doua perechi de pointeri (pozitiile celui mai din stanga, respectiv din dreapta copil din interval si pozitiile celui mai apropiat scaun liber din afara intervalului in stanga, respectiv in dreapta), realizand maxim $N$ pasi la fiecare query.

h3. <tex>O((N + Q) * log(N))</tex> timp, <tex>O(N * log(N))</tex> memorie
 
Daca ne uitam la copiii din intervalul dintr-un query, un prefix al lor va merge in stanga iar sufixul ramas (complementarul) va merge in dreapta. Astfel, stim ca pentru orice $K$ cu $2 * K &le; R - L + 1$, fie primii $K$ copii vor merge in stanga, fie ultimii $K$ copii vor merge in dreapta, daca nu chiar ambele (dar nu ne intereseaza cazul acesta, deoarece se va trata de la sine). Extrapoland _greedyul_ prezentat anterior, stim ca este bine sa facem acea serie de mutari (dintre cele doua mentionate adineauri) care are costul mai mic. Dupa mutari, se va ajunge la o situatie asemanatoare, careia i se va aplica acelasi algoritm, poate cu un $K$ diferit, pana cand va ramane un singur copil de mutat din interval, a carui alegere a destinatiei este facila.
 
Plecand de la aceste observatii, ne vom alege un $K$ convenabil astfel incat sa fi putut precalcula costul ipotetic al mutarii a $K$ copii in stanga sau in dreapta, plecand de la o pozitie data, dar sa si putem scoate din interval cat mai multi copii, in asa fel incat sa nu repetam procedeul de prea multe ori. Considerandu-l pe $K$ intotdeauna o putere a lui $2$, se vor obtine rezultate frumoase: cu precalcularea $d[directie][t][pozitie_start] = pair < costul minim de a trimite 2^{_t_}^ copii plecand de la _pozitie start_ in directia stanga sau dreapta, in functie de _directie_ (care este un $bool$) ; pozitia primului scaun liber in directia data de _directie_ daca se ocupa 2^{_t_}^ scaune plecand de la _pozitie_start_ >$ si cu alegerea celui mai mare $K$ putere de $2$ care sa satisfaca restrictia de mai sus la fiecare interogare, se poate obtine un algoritm de complexitatea mentionata mai sus, care rezolva queryurile unul cate unul, pe masura ce le intampina.

h3. ...

h2. Solutia 2