| Fişierul intrare/ieşire: | memorie.in, memorie.out | Sursă | ad-hoc |
| Autor | clasica | Adăugată de |  Catalin Francu •Catalin.Francu |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 2048 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Memorie
În junglă, elefantul se laudă cu memoria lui de... elefant. Iepuraşul îi propune un joc ca să-l testeze. Jocul foloseşte un pachet standard de cărţi de joc. De N ori, ei extrag câte o carte. În secret, iepuraşul îşi notează cartea. Apoi reintroduc cartea în pachet şi amestecă pachetul. La final, iepuraşul îi pune elefantului Q întrebări de forma: între extragerile x şi y inclusiv, câte cărţi distincte au apărut?
Elefantul, de fapt, este cam senil, aşa că vă roagă să îl ajutaţi.
Date de intrare
Fişierul de intrare memorie.in conţine pe prima linie numerele N şi Q. Pe a doua linie apar cele N cărţi extrase, separate prin spaţii. Pe următoarele Q linii apare câte o întrebare sub forma unei perechi de numere, x y.
Date de ieşire
În fişierul de ieşire memorie.out se vor afişa răspunsurile la întrebări, câte unul pe linie.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ Q ≤ 200.000
- 1 ≤ x ≤ y ≤ N
- Pentru simplitate, cărţile sunt codificate prin numere de la 1 la 52.
Exemplu
| memorie.in | memorie.out | Explicaţie |
|---|---|---|
| 8 4 7 43 7 21 35 7 7 7 2 7 3 5 6 8 2 2 | 4 3 1 1 | Intervalul [43 7 21 35 7 7] conţine numerele distincte 43, 7, 21, 35. Intervalul [7 21 35] conţine numerele distincte 7, 21, 35 Intervalul [7 7 7] conţine doar numărul distinct 7. Intervalul [43] conţine un singur număr, 43. |
