h2. Restrictii

'* $1$ ≤ $N$, $M$ ≤ $50.000$

* $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^$;

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

O rezolvare brute a problemei ar obtine in jur de 30 puncte si o poti gasi 'aici':job_detail/147099?action=view-source. 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':/job_detail/147101?action=view-source.

h2. Probleme similare