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

h2. Indicatii pentru rezolvare

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.
 
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.

O rezolvare brute ar obtine in jur de 30-40 puncte si o poti gasi "aici":job_detail/143960?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.

h2. Probleme similare

* 'Datorii':problema/datorii, 'Farfurii':problema/farfurii, 'Hotel':problema/hotel, 'Delay':problema/delay, 'Parcele':problema/parcele, 'Zoo':problema/zoo, 'Demolish':problema/demolish, 'SequenceQuery':problema/sequencequery, 'Biscuiti':problema/biscuiti, 'Order':problema/order, 'Omizi':problema/omizi, 'Eq':problema/eq, 'Zeap':problema/zeap, 'Namlei':problema/namlei, 'Schi':problema/schi, 'Maxq':problema/maxq, 'Eliminare':problema/eliminare, 'Sea2':problema/sea2, "Supper":http://www.spoj.pl/problems/SUPPER/, "Cartesian Tree":http://acm.sgu.ru/problem.php?contest=0&problem=155, "Fence obstacle course":http://acm.pku.edu.cn/JudgeOnline/problem?id=2374, "Atac":http://campion.edu.ro/problems/3/302/atac_ro.htm
== include(page="template/taskfooter" task_id="arbint") ==

2765