Fişierul intrare/ieşire:arbint.in, arbint.outSursăad-hoc
AutorArhiva EducationalaAdăugată decos_minBondane Cosmin cos_min
Timp execuţie pe test0.5 secLimită de memorie36480 kbytes
Scorul tăuN/ADificultateN/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 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.inarbint.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content