Algoge Judge

Editorial for DodPomOduPod

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: DuX

Primetimo da kada sortiramo niz, nijedan upit neće promeniti redosled elemenata, već samo vrednosti nekima od njih.

To znači da binarnom pretragom možemo naći najmanji indeks $x$ ~x~ takav da nakon što izvršimo sve upite nad $A[x]$ ~A[x]~, važi $A[x] \geq L$ ~A[x] \geq L~. Ovo radimo tako što jednostavno za fiksirano $x$ ~x~ izvršimo sve upite redom, u složenosti $O(N)$ ~O(N)~. Pošto ćemo proveriti najvise $O(\log{N})$ ~O(\log{N})~ indeksa, ukupna složenost će biti $O(N\log{N})$ ~O(N\log{N})~.

Slično, možemo da nađemo najveći indeks $y$ ~y~ za koji je nakon što izvršimo sve upite nad $A[y]$ ~A[y]~ važi $A[y] \leq R$ ~A[y] \leq R~.

Ovime smo upravo i našli broj traženih elemenata: $y-x+1$ ~y-x+1~, odnosno svi elementi iz segmenta $i \in [x,y]$ ~i \in [x,y]~ zadovoljavaju $L \leq A[i] \leq R$ ~L \leq A[i] \leq R~ nakon izvršenih upita.

Potrebno je obratiti posebnu pažnju pri obrađivanju međurezultata kod upita zato što brojevi mogu ispasti iz granica long long-a, odnosno 64-bitovnog tipa podataka.

Zadatak je preuzet sa $\texttt{Moscow}$ ~\texttt{Moscow}~ $\texttt{Autumn}$ ~\texttt{Autumn}~ $\texttt{Workshop}$ ~\texttt{Workshop}~ $\texttt{2019}$ ~\texttt{2019}~ $\texttt{Day}$ ~\texttt{Day}~ $\texttt{4}$ ~\texttt{4}~, takmičenje $\texttt{JAG}$ ~\texttt{JAG}~ $\texttt{2019++}$ ~\texttt{2019++}~.

Comments

There are no comments at the moment.