Ricerca binaria sinistra e destra
Problem
Dati due elenchi di numeri, i numeri nel primo elenco sono in ordine non decrescente. Per ogni numero nel secondo elenco, determina il numero della prima e dell'ultima occorrenza di quel numero nel primo elenco.
Inserimento:
- la prima riga dell'input contiene due numeri N e M (\(1<=N,\ M <=20000\));
- la seconda riga contiene N numeri interi non decrescenti — elementi della prima lista;
- la terza riga contiene M di numeri interi non negativi - elementi del secondo elenco.
Tutti i numeri negli elenchi sono interi con segno a 32 bit.
Output: Il programma dovrebbe produrre righe M. Per ogni numero del secondo elenco, stampa il numero della sua prima e ultima occorrenza nel primo elenco. La numerazione parte da uno. Se il numero non รจ incluso nel primo elenco, devi stampare un singolo numero 0.
Esempi
| # |
Input |
Uscita |
| 1 |
105
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
|
10 10
3 4
7 7
1 2
0
|