K-th Set Bit (K-ésimo bit en 1)
Se te proporciona un arreglo binario de tamaño
n, compuesto por 0s y 1s, en el que los elementos están numerados del 1 al n. Necesitas procesar q consultas, de las cuales hay dos tipos:- Consulta de tipo 1: Encontrar el índice de la
k-ésima aparición de 1 en el arreglo.
- Consulta de tipo 2: Actualizar el valor en un índice específico del arreglo.
Tu objetivo es escribir un programa que responda estas consultas de manera eficiente.
Entrada
La entrada comienza con dos enteros
n y q separados por un espacio, que representan el tamaño del arreglo binario y la cantidad de consultas, respectivamente.La segunda línea contiene
n elementos binarios del arreglo.Las siguientes
q líneas describen las consultas. Cada consulta está formada por un tipo de consulta (1 o 2) seguido de los parámetros necesarios:- Para la consulta de tipo 1: un entero
k(1 ≤ k ≤ n).
- Para la consulta de tipo 2: un índice
p(1 ≤ p ≤ n) y un valor (0 o 1) que se actualizará en esa posición.
Salida
Para cada consulta de tipo 1, imprime el índice de la
k-ésima aparición de 1 en el arreglo. Si no existe dicha aparición, imprime -1.Ejemplos
Entrada | Salida |
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