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 A_i 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 ≤ A_i ≤ 10⁹ pentru 1 ≤ i ≤ N
• Pentru operatia de tip 0: 1 ≤ a ≤ b ≤ N 
• Pentru operatia de tip 1: 1 ≤ a ≤ N si 1 ≤ b ≤ 10⁹ 

Exemplu

Indicatii pentru rezolvare

O rezolvare brute ar obtine in jur de 30-40 puncte si o poti gasi 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

Cum se trimit solutii?