K-ième bit à 1
On vous donne un tableau binaire de taille
n, composé de 0 et de 1, où les éléments du tableau sont numérotés de 1 à n. Vous devez traiter q requêtes, chacune pouvant être de deux types :- Requête de type 1 : Trouver l’indice de la
k-ième occurrence de 1 dans le tableau.
- Requête de type 2 : Mettre à jour la valeur d’un indice spécifique du tableau.
Écrivez un programme qui réponde efficacement à ces requêtes.
Entrée
La première ligne de l’entrée contient deux entiers
n et q séparés par un espace, représentant respectivement la taille du tableau binaire et le nombre de requêtes.La deuxième ligne contient
n éléments binaires du tableau.Les
q lignes suivantes décrivent les requêtes. Chaque requête est définie par un type (1 ou 2), suivi des paramètres nécessaires :- Pour une requête de type 1 : un entier
k(1 ≤ k ≤ n).
- Pour une requête de type 2 : un entier
p(1 ≤ p ≤ n) et une valeur ( ou ) à insérer à cet indice pour la mise à jour.
Sortie
Pour chaque requête de type 1, affichez l’indice correspondant à la
k-ième occurrence de 1 dans le tableau. S’il n’existe pas de k-ième occurrence, affichez -1.Exemples
Input | Entrée |
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