Lista de probleme 2

Se dă o permutare P a mulțimii {1,2, … ,N}. Se mai dau Q întrebări specificate prin câte un număr D.

Dacă D este pozitiv trebuie să determinăm a D-a permutare care succede lexicografic P iar dacă D este negativ, a D-a permutare care precede lexicografic P.

În Bistriţa sunt N copii, fiecare dintre ei având un număr preferat Xi . Copii se aşează pe un rând, cu poziţiile numerotate de la 1 la N. După ce copii s-au aşezat, profesoara de educaţie fizică le cere să execute M mişcări de tipul (a, b), cu semnificaţia că îşi vor schimba ordinea copiii care se află între poziţiile a şi b, inclusiv.

Să se răspundă la Q întrebări de tipul p, cu semnificaţia: care este numărul preferat al copilului, care se află pe poziţia p, după executarea mişcărilor cerute de profesoara de educaţie fizică.