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 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB