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 pozitia $a$ va deveni $b$.

{*} $1$ $a$ $b$ - Valoarea elementului de pe pozita $a$ va deveni $b$.

h2. Date de intrare

O rezolvare brute ar obtine in jur de 30-40 puncte si o poti gasi "aici":job_detail/143960?action=view-source.

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":multe-smenuri-de-programare-in-cc-si-nu-numai. Aceasta solutie obtine in jur de 50 puncte si o gasesti "aici":job_detail/156345?action=view-source.

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":multe-smenuri-de-programare-in-cc-si-nu-numai. Aceasta solutie obtine in jur de 50 puncte si o gasesti "aici":http://infoarena.ro/job_detail/156345?action=view-source.

Solutia optima pentru rezolvarea problemei are complexitatea O({$M$}{$logN$}) si se poate realiza prin intermediul "arborilor de intervale":arbori-de-intervale. O solutie de 100 puncte pe ideea prezentata in articol gasesti "aici":job_detail/143961?action=view-source.

== include(page="template/taskfooter" task_id="arbint") ==

==SmfTopic(topic_id="2765")==

2765