Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arbint.in, arbint.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Bondane Cosmin •cos_min |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 36480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Arbori de intervale
Fie un vector A cu N elemente naturale. Asupra lui se vor face Q operatii de forma x, b, c, codificate astfel in fisierul de intrare:
• 0 a b - Sa se determine minimul si maximul din intervalul [a,b].
• 1 a b - Valoarea elementului de pe pozita a va deveni b.
Date de intrare
Pe prima linie a fisierului de intrare se afla N si Q. Pe urmatoarea linie se gasesc cele N elemente ale vectorului, iar urmatoarele linii descriu operatia care trebuie efectuata.
Date de iesire
In cazul unei operatii de tip 0, se va scrie pe o singura separata minimul si maximul cerut(in ordinea ceruta in fisierul de intrare).
Restrictii
- 1 ≤ N,Q ≤ 100000
- 1 ≤ elementele vectorului A ≤ 109
Exemplu
| arbint.in | arbint.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Indicatii pentru rezolvare
Problema se poate rezolva in mai multe moduri. O rezolvare brute gasesti aici si optine in jur de 30 puncte. O rezolvare optima a problemei are complexitatea O(N*logN) si se poate realiza prin intermediul arborilor de intervale. Pentru o solutie incearca aici sau pentru articolu aici.
