Lista de probleme 23

Se dă un șir de matrice pătratice asupra căruia se pot face două tipuri de operații: actualizare a unui element (se înlocuiește matricea de pe acea poziție cu alta) și interogarea unui interval de indici (determinarea produsului matricelor memorate între cei doi indici, inclusiv).

Se dau N segmente în plan, fiecare fiind paralel cu una dintre axele de coordonate. Determinați numărul total de puncte de intersecție între două segmente.

Se dă un şir a cu n numere naturale. Aflaţi numărul tripletelor (i,j,k), cu 1 ≤ i < j < k ≤ n, pentru care avem a[i] > a[j] < a[k].

Miruna şi partenerul ei de aventură, Pikachu, sunt în faţa unei noi provocări. Cele două personaje au ajuns lângă un lanţ muntos format din N vârfuri aşezate în linie dreaptă unul după altul. Pentru fiecare vârf muntos se cunoaşte înălţimea lui. Folosindu-se de puterile sale extraordinare, Pikachu este capabil sa scadă sau să crească înălţimea unui vârf muntos cu o unitate într-o secundă. Din motive necunoscute muritorilor de rând, cei doi prieteni vor să obţină cel puţin K vârfuri montane consecutive care au aceeaşi înălţime, într-un timp cât mai scurt. Determinaţi timpul minim în care Pikachu poate îndeplini această sarcină.

Se dă un șir v format din N elemente naturale nenule nu neapărat distincte. Asupra șirului putem aplica un singur tip de operație: interschimbarea a două elemente aflate pe poziții consecutive. Dându-se un număr natural K, se cere șirul minim lexicografic ce se poate obține prin aplicarea a cel mult K interschimbări de elemente de pe poziții consecutive.

Se dă un șir de N numere și Q operații de tipul:

• 0 a b val : se va aduna valoarea val la toate numerele din intervalul [a, b].
• 1 a b : se va afișa elementul minim par și elementul maxim impar din intervalul [a, b]; în cazul în care unul dintre aceste numere nu există, se va afișa -1 în locul său.

Răspundeți corect la toate operațiile de tip 1.

Interviul de admitere la prestigioasa Universitate Cambridge constă în N probleme, numerotate de la 1 la N. Alex este în momentul acesta acolo, așteptând să susțină interviul. Takahiro Wong, care tocmai a ieșit din examen, a rezolvat toate problemele, problema i rezolvând-o după Di secunde de la începerea interviului. Cunoscând ca poate rezolva fiecare problema i în Ti secunde, Alex, panicat din fire, își pune M întrebări de forma: x y. Pentru fiecare întrebare, Alex vrea să afle dacă poate rezolva fiecare problemă din intervalul [x;y] înaintea lui Takahiro Wong (Alex poate rezolva problemele din intervalul [x;y] în ce ordine dorește). Ajutați-l pe Alex să răspundă corect la cele M întrebări pentru a nu intra panicat la interviu.

Dat fiind un vector de n elemente și q actualizări, să se afle după fiecare actualizare ce valoare este atinsă de cele mai multe ori din vector.

RAU-Gigel testează un joc cu trageri și premii. Jocul constă într-o serie de acțiuni care au loc la anumite momente de timp. Acțiunile pot fi: aparițiile unor premii sau trageri. Premiile apar la anumite înălțimi, pentru un interval de timp bine definit. Tragerile au loc la anumite momente de timp și se propagă în spațiu instantaneu. RAU-Gigel câștigă câte un punct pentru fiecare premiu ochit. Câte puncte câștigă RAU-Gigel la fiecare tragere și câte în total?

Tsubasa-chan adoră dulciurile! De curând a apărut un nou tip de desert. Astfel decide să înfăptuiască o nouă fabrică care să producă acest produs delicios. Fabrica conține un container imens pătratic, plin de aluat, de 106 x 106 unități. Fiecare punct din container are drept coordonate o pereche de numere reale (x, y), unde 0 ≤ x, y ≤ 106, iar fiecare punct are o dulceață. Dându-se toate operațiile întreprinse în producerea desertului, să se găsească dulcețurile totale ce sunt găsite la toate operațiile de degustare.