Lista de probleme 4

Fie un șir de caractere S format din litere mici ale alfabetului englez, indexat de la 1. Trebuie să răspundeți la Q query-uri de forma x, y – calculați câte inversiuni se află în intervalul [x, y]. O inversiune este o pereche de indici (i, j), 1 ≤ i < j ≤ N, pentru care este adevărată relația Si > Sj.

Premierul Marii Britanii, Rishi Sunak, a decis să reorganizeze structura administrativă a comitatului Oxfordshire. În Oxfordshire sunt prezente N orașe numerotate de la 1 la N, conectate prin M autostrăzi (drumuri unidirecționale ce conectează două orașe). Rishi a hotărât ca toate orașele cu proprietatea că cetățenii tuturor celorlalte orașe pot ajunge în ele prin intermediul autostrăzilor să devină reședințe. Deoarece numărul de orașe și autostrăzi din Oxfordshire este foarte mare, Rishi vă cere ajutorul în rezolvarea a două probleme cheie.
1. Care sunt indicii orașelor reședință din Oxfordshire.
2. Care este distanța minimă de la fiecare oraș până la cea mai apropiată reședință de acel oraș.

Emilian este un ilustru doctor în neurochirurgie, ce tocmai și-a deschis o clinică în orașul Sfîantul Genesius. Deoarece este cunoscut în tot orașul ca fiind cel mai bun neurochirurg din țară, mereu există o mulțime de cereri de la pacienții ce doresc să fie programați la o consultație. Pentru că în mod normal este foarte ocupat, el lasă secretariatul clinicii să se ocupe de programări. Din păcate, tot personalul secretariatului este plecat în vacanță fix în perioada cea mai aglomerată a anului și astfel Emilian vă cere ajutorul pentru a-și programa pacienții. Într-o zi el primește cereri de la N pacienți, iar pentru a-i fi mai ușor să-și facă programul, Emilian a permis fiecărui pacient să-i propună doar câte două momente de timp în care să poată fi chemat la consult. Știind că personalul lui Emilian este plecat timp de T zile, iar în fiecare zi Emilian are alți pacienți pe care trebuie să îi programeze, ajutați-l să decidă pentru fiecare zi, dacă poate sau nu să programeze toți pacienții din acea zi.

Cercetătorii din cadrul proiectului LHC (Large Hadron Collider) de la Geneva au anunțat descoperirea unei noi forme a materiei: flatquarkon. Putem reprezenta masa întregului sistem printr-o matrice cu N linii și M coloane unde mij reprezintă masa quarcului aflat pe linia i și coloana j.
Aplicând un câmp magnetic perpendicular pe planul unui flatquarkon, putem activa energetic unul sau mai mulți quarci, aceștia devenind capabili să participe în reacții nucleare. Dacă doi quarci activi sunt adiacenți (se învecinează pe linie sau pe coloană), atunci vor participa împreună în orice reacție nucleară. Considerăm un flatquarkon aflat într-un mediul lipsit de câmpuri magnetice. Se dă o listă de Q instrucțiuni de două tipuri:
1. Se aplică un câmp magnetic asupra quarkului de pe linia i și coloana j. Dacă quarkul este inactiv, acesta va fi activat de câmpul magnetic. Dacă este deja activ, nu se va întâmpla nimic.
2. Să se afle energia maximă degajată într-o reacție nucleară între două zone active ale flatquarkon-ului. O zonă activă este o porțiune conexă a matricii (toți quarcii incluși sunt adiacenți) ce conține doar quarci activi și are dimensiune maximă (nu se mai poate adăuga niciun alt quark activ fără a încălca proprietatea de conexitate).