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

Fie un vector $A$ cu $N$ elemente naturale. Asupra lui se vor face $Q$ operatii de forma $x$, $b$, $c$, codificate astfel in fisierul de intrare:
{*} $0$ $a$ $b$ - Sa se determine minimul si maximul din intervalul [$a$,{$b$}].

Fie un vector $A$ cu $N$ elemente naturale. Asupra lui se vor face $M$ operatii de forma $x$, $b$, $c$, codificate astfel in fisierul de intrare:
{*} $0$ $a$ $b$ - Sa se determine maximul din intervalul [$a$,{$b$}].

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

Pe prima linie a fisierului de intrare se afla $N$ si $Q$. Pe urmatoarea linie se gasesc cele $N$ elemente ale vectorului, iar urmatoarele linii descriu operatia care trebuie efectuata.

Pe prima linie a fisierului de intrare se afla $N$ si $M$. Pe urmatoarea linie se gasesc cele $N$ elemente ale vectorului, iar urmatoarele linii descriu operatia care trebuie efectuata.

h2. Date de iesire

In cazul unei operatii de tip $0$, se va scrie pe o singura separata minimul si maximul cerut(in ordinea ceruta in fisierul de intrare).

Pentru fiecare operatie de tip $0$, se va afisa pe cate o linie maximul pentru intervalul cerut(in ordinea ceruta in fisierul de intrare).

h2. Restrictii

* $1$ ≤ $N$,{$Q$} ≤ $100000$

* $1$ ≤ {$M$}, {$Q$} ≤ $100000$

* $1$ ≤ elementele vectorului $A$ ≤ $10^9^$
h2. Exemplu

h3. Indicatii pentru rezolvare

Problema se poate rezolva in mai multe moduri. O rezolvare brute gasesti aici si optine in jur de 30 puncte. O rezolvare optima a problemei are complexitatea O({$N$}*{$logN$}) si se poate realiza prin intermediul arborilor de intervale. Pentru o solutie incearca aici sau pentru articolu "aici":http://infoarena.ro/arbori-de-intervale.

O rezolvare brute ar obtine in jur de 30-40 puncte. O rezolvare optima a problemei are complexitatea O({$M$}{$logN$}) si se poate realiza prin intermediul "arborilor de intervale":http://infoarena.ro/arbori-de-intervale. O solutie de 100 puncte pe ideea prezentata in articol gasesti aici.

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