Fişierul intrare/ieşire: | arbint.in, arbint.out | Sursă | ad-hoc |
Autor | Arhiva Educationala | Adăugată de | |
Timp execuţie pe test | 0.25 sec | Limită de memorie | 36480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
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 pozitia 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 a 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