K-te gesetzte Bit
Sie haben ein Binärarray der Größe
n, das aus 0 und 1 besteht. Die Elemente dieses Arrays sind durchnummeriert von 1 bis n. Es müssen q Anfragen (Queries) bearbeitet werden, die jeweils einen von zwei Typen haben:- Query Typ 1: Finden Sie den Index des
k-ten Auftretens von 1 im Array.
- Query Typ 2: Aktualisieren Sie den Wert an einer bestimmten Position im Array.
Schreiben Sie ein Programm, das diese Anfragen effizient bearbeitet.
Eingabe
Die Eingabe beginnt mit zwei Ganzzahlen
n und q in der ersten Zeile, getrennt durch ein Leerzeichen. Sie geben die Größe des Binärarrays bzw. die Anzahl der Queries an.Die zweite Zeile enthält die
n binären Elemente des Arrays.Die folgenden
q Zeilen beschreiben die Queries. Jede dieser Zeilen beginnt mit einem Query-Typ (1 oder 2), dem die nötigen Parameter folgen:- Bei einem Query vom Typ 1: eine ganze Zahl
k(1 ≤ k ≤ n).
- Bei einem Query vom Typ 2: ein ganzzahliger Index
p(1 ≤ p ≤ n) und ein Wert ( oder ), mit dem an dieser Stelle aktualisiert wird.
Ausgabe
Für jede Anfrage vom Typ 1 sollen Sie den Index des
k-ten Auftretens von 1 im Array ausgeben. Falls ein solches k-tes Auftreten nicht existiert, geben Sie -1 aus.Beispiele
Eingabe | Ausgabe |
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