K-th Set Bit
É-lhe fornecido um array binário de tamanho
n, composto por 0s e 1s, em que os elementos do array estão numerados de 1 a n. É necessário processar q consultas, com cada consulta a poder ser de dois tipos:- Tipo de consulta 1: Encontrar o índice da
k-ésima ocorrência de 1 no array.
- Tipo de consulta 2: Atualizar o valor num índice específico do array.
Escreva um programa que consiga responder de forma eficiente a estas consultas.
Entrada
Na primeira linha, são fornecidos dois inteiros
n e q, separados por um espaço, que representam o tamanho do array binário e o número de consultas, respetivamente.Na segunda linha, surgem os
n elementos binários do array.Nas
q linhas seguintes, são apresentadas as consultas. Cada consulta é descrita por um tipo (1 ou 2), seguido dos parâmetros necessários:- Para o tipo de consulta 1: um inteiro
k(1 ≤ k ≤ n).
- Para o tipo de consulta 2: um índice inteiro
p(1 ≤ p ≤ n) e um valor ( ou ) para atualizar nesse índice.
Saída
Para cada consulta do tipo 1, imprima o índice da
k-ésima ocorrência de 1 no array. Se não existir esta k-ésima ocorrência, imprima -1.Exemplos
Input | Entrada |
6 4
1 0 1 1 0 1
1 2
2 1 0
1 4
1 3 | 3
-1
6 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB