Pesquisa binária esquerda e direita
Problem
Dadas duas listas de números, os números da primeira lista estão em ordem não decrescente. Para cada número na segunda lista, determine o número da primeira e última ocorrência desse número na primeira lista.
Entrada:
- a primeira linha da entrada contém dois números N e M (\(1<=N,\ M <=20000\));
- a segunda linha contém N inteiros não decrescentes — elementos da primeira lista;
- a terceira linha contém M de inteiros não negativos - elementos da segunda lista.
Todos os números nas listas são inteiros assinados de 32 bits.
Saída: O programa deve gerar M linhas. Para cada número da segunda lista, imprima o número de sua primeira e última ocorrência na primeira lista. A numeração começa a partir de um. Se o número não estiver incluído na primeira lista, você precisará imprimir um único número 0.
Exemplos
| # |
Entrada |
Saída |
| 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
|