Pred Zimske olimpijske igre, organizator svakodnevno meri visinu snega. Nekad i više puta dnevno. Rezultati merenja dostupni su svima. Američka reprezentacija veruje da može pomoći svojim skijašima ako detaljno analizira ove podatke. Primetili su da se visina snega s vremenom nikako ne smanjuje. Međutim, često im je bio potreban odgovor na pitanje: Koliko se različitih visina pojavljuje između dva merenja (računajući i ta merenja)? Njihovim programerima je trebalo previše vremena da odgovore na ova pitanja, pa su zamolili vas za pomoć.
Ulaz
U prvom redu standardnog ulaza nalazi se broj , broj rezultata merenja. U drugom redu nalazi se prirodnih brojeva, koji predstavljaju rezultate (visinu snega), u redosledu merenja. U trećem redu nalazi se broj , broj upita Američke reprezentacije. U sledećih redova nalaze se dva cela broja i koji predstavljaju redne brojeve dva merenja (merenja su indeksirana brojevima od do ).
Izlaz
Standardni izlaz sadrži celih brojeva, svaki u novom redu, koji predstavljaju odgovore na pitanje Američke reprezentacije za data dva merenja. U -tom redu nalazi se odgovor na -ti upit.
Primer 1
Ulaz
10
1 2 2 2 4 4 5 6 7 7
5
0 9
1 3
1 5
7 9
4 4
Izlaz
6
1
2
2
1
Objašnjenja primera
U prvom upitu rezultati koji se pojavljuju su , , , , i . U drugom to je samo . Između merenja broj i broj pojavljuju se rezultati i .
Ograničenja
.
.
Visina snega je veća od a manja od .
Test primeri su podeljeni u tri disjunktne grupe:
U testovima vrednim 30 poena: .
U testovima vrednim 30 poena: i visina snega je manja od 500.
U testovima vrednim 40 poena: Bez dodatnih ograničenja.
Autor
Tekst i test primeri
Analiza rеšenja
Testiranje
Marko Baković
Marko Baković
Nepoznato
Aleksandar Ivanović
Za svaki interval, prolaskom od levog do desnog kraja, možemo naći broj različitih brojeva koje sadrži tako što ćemo brojati samo prvo pojavljivanje svakog broja. Kako ćemo znati da je neko pojavljivanje prvo? Znamo da je niz sortiran, pa važi da je pojavljivanje broja prvo ako je taj broj ili prvi broj unutar intervala, ili je broj različit od svog prethodnika (broja levo od njega). Vremenska složenost po upitu je , pa je složenost ovog rešenja . Memorijska složenost je . Ovo rešenje donosi poena.
Neka je broj pojavljivanja broja u nizu na pozicijama od do . Važi sledeće:
Koristeći ovo, cnt možemo odrediti u složenosti gde je najveći broj u nizu. Za svaki interval možemo u složenosti da odredimo da li se broj pojavljuje unutar intervala tako što je broj pojavljivanja broja unutar jednak . Sada na svaki upit možemo odgovoriti prolaskom od do i proverom za svaki broj da li se pojavljuje unutar intervala iz upita. Vremenska složenost ovog rešenja je , a memorijska . Ovo rešenje takođe vredi poena, ali može se primeniti u kombinaciji sa prethodnim rešenjem tako što ukoliko je radimo u složenosti , a inače u složenosti , i ovakva kombinacija vredi poena.
Analizirajmo sada rešenje za poena. Posmatrajmo samo prvo pojavljivanje svakog broja u nizu. Neka je broj ovih prvih pojavljivanja u nizu na pozicijama od do . Broj različitih brojeva na intervalu jednak je broju prvih pojavljivanja na intervalu. Već smo rekli da je pojavljivanje broja prvo ako je taj broj ili prvi broj unutar intervala, ili je broj različit od svog prethodnika. Broj onih koji su različiti od svog prethodnika na intervalu jednak je . Međutim, u slučaju da je , tada rešenje treba uvećati za jer nismo računali broj sa indeksom jer je on jednak svom prethodniku, a treba ga računati zato što je prvi broj unutar intervala. Dakle, rešenje za interval je:
Niz kreiramo u složenosti , i kada imamo taj niz, na upite odgovaramo u . Vremenska složenost ovog rešenja je , a memorijska .