K-th Set Bit (K-esimo bit impostato)
Vi viene fornito un array binario di dimensione
n, composto da 0 e 1, i cui elementi sono numerati da 1 a n. Dovete gestire q query, ognuna delle quali può essere di due tipi:- Query di tipo 1: trovare l’indice della
k-esima occorrenza di 1 nell’array.
- Query di tipo 2: aggiornare il valore in una determinata posizione dell’array.
Scrivete un programma in grado di rispondere a queste query in modo efficiente.
Input
L’input è costituito da due interi
n e q sulla prima riga, separati da uno spazio, che rappresentano la dimensione dell’array binario e il numero di query, rispettivamente.La seconda riga contiene i
n elementi binari dell’array.Le successive
q righe descrivono le query. Ogni query è caratterizzata da un tipo (1 o 2) seguito dai parametri necessari:- Per la query di tipo 1: un intero
k(1 ≤ k ≤ n).
- Per la query di tipo 2: un indice intero
p(1 ≤ p ≤ n) e un valore (0 o 1) da aggiornare in quella posizione.
Output
Per ogni query di tipo 1, stampate l’indice della
k-esima occorrenza di 1 nell’array. Se la k-esima occorrenza non esiste, stampate -1.Esempi
Ingresso | Uscita |
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