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 M operatii, codificate astfel in fisierul de intrare:
• 0 a b - Sa se determine maximul din intervalul [a,b] (maximul dintre valorile Ai cu a ≤ i ≤ 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 M. Pe urmatoarea linie se gasesc cele N elemente ale vectorului, iar urmatoarele M linii descriu operatia care trebuie efectuata.
Date de iesire
Pentru fiecare operatie de tip 0, se va afisa pe cate o linie maximul pentru intervalul cerut (in ordinea ceruta in fisierul de intrare).
Restrictii
- 1 ≤ M, N ≤ 100000
- 0 ≤ Ai ≤ 109 pentru 1 ≤ i ≤ N
- Pentru operatia de tip 0: 1 ≤ a ≤ b ≤ N
- Pentru operatia de tip 1: 1 ≤ a ≤ N si 1 ≤ b ≤ 109
Exemplu
| arbint.in | arbint.out |
|---|---|
| 5 5 4 3 5 6 1 0 1 3 1 3 2 0 2 3 1 4 2 0 1 5 | 5 3 4 |
Indicatii pentru rezolvare
O rezolvare brute ar obtine in jur de 30-40 puncte si o poti gasi aici.
O alta rezolvare posibila este una care raspunde la query in O(sqrtN). Ideea este de imparti sirul initial in bucati de lungime sqrtN. Pentru mai multe detalii poti citi aici. Aceasta solutie obtine in jur de 50 puncte si o gasesti aici.
Solutia optima pentru rezolvarea problemei are complexitatea O(MlogN) si se poate realiza prin intermediul arborilor de intervale. O solutie de 100 puncte pe ideea prezentata in articol gasesti aici.
Probleme similare
Iata o lista cu probleme care se pot rezolva folosind aceasta structura de date. Problemele nu sunt intr-o anumita ordine, unele probleme din lista sunt dificile si folosesc si alte tehnici de programare, asa ca nu fiti dezamagiti daca nu veti gasi solutii la toate.
- Datorii, Farfurii, Hotel, Delay, Parcele, Zoo, Demolish, SequenceQuery, Biscuiti, Order, Omizi, Eq, Zeap, Namlei, Schi, Maxq, Eliminare, Sea2, Supper, Cartesian Tree, Fence obstacle course, Atac
