Pagini recente » Atasamentele paginii Cai2 | Diferente pentru problema/hardtask intre reviziile 13 si 40 | Diferente pentru problema/brazi intre reviziile 13 si 14 | Atasamentele paginii Pusculita | Diferente pentru problema/aib intre reviziile 3 si 4
Diferente pentru
problema/aib intre reviziile
#3 si
#4
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="aib") ==
Se da 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 suma elementelor intervalului [a,b]
{*} 1 $a$ $b$ - Valoarea elementului de pe pozitia $a$ va deveni $b$.
{*} 0 $a$ $b$ - Sa se determine suma valorilor elementelor intervalului [a,b].
{*} 1 $a$ $b$ - Valorii elementului de pe pozitia $a$ ii se va adauga valoarea $b$.
h2. Date de intrare
h2. Restrictii
* $1$ ≤ $N$, $M$ ≤ $100000$
'* $1$ ≤ $N$, $M$ ≤ $50.000$
* $0 ≤ A{~i~} ≤ 10^4^$ 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^4^$;
* Rezultatul se va incadra pe $32$ de biti
h2. Exemplu
table(example). |_. aib.in |_. aib.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 5
3 8 4 7 8 8
0 1 5
0 6 6
1 4 4
1 2 9
1 1 9
| 30
8
|
h3. Explicatie
h2. Solutie
...
O rezolvare brute a problemei ar obtine in jur de 30 puncte si o poti gasi 'aici':. Solutia optima pentru rezolvare a problemei are complexitate O({$MlogN$}) si se poate realiza prin intermediul 'arborilor indexati binar':. O solutie de 100 puncte pe ideea aceasta gasesti 'aici':.
h2. Probleme similare
* 'Datorii':problema/datorii
== include(page="template/taskfooter" task_id="aib") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.