Diferente pentru problema/arbint intre reviziile #10 si #27

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="arbint") ==
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$}].
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$.
h2. 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 $M$ 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 $M$ linii descriu operatia care trebuie efectuata.
h2. 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).
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$ ≤ {$M$}, {$Q$} ≤ $100000$
* $0$ ≤ elementele vectorului $A$ ≤ $10^9^$
* Pentru operatia de tip {$0$}: $1$ ≤ {$a$} ≤ {$b$} ≤ $N$
* Pentru operatia de tip {$1$}: $1$ ≤ {$a$} ≤ $N$ si $1$ ≤ {$b$} ≤ $10^9^$
* $1 ≤ M, N ≤ 100000$
* $0 ≤ A{~i~} ≤ 10^9^$ 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^9^$
h2. Exemplu
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. 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.
 
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.
h2. Probleme similare
* "Datorii":http://infoarena.ro/problema/datorii
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':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") ==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
2765