K-th Set Bit (k-й установленный бит)
Вам дан бинарный массив размера
n, состоящий из 0 и 1, где элементы массива нумеруются от 1 до n. Необходимо обработать q запросов, каждый из которых относится к одному из двух типов:- Запрос типа 1: найти индекс
k-го вхождения 1 в массиве.
- Запрос типа 2: обновить значение в массиве по заданному индексу.
Ваша задача — написать программу, которая будет эффективно отвечать на эти запросы.
Входные данные
На первой строке содержатся два целых числа
n и q, разделённые пробелом, обозначающие размер бинарного массива и количество запросов соответственно.На второй строке записаны
n бинарных элементов массива.Следующие
q строк содержат описания запросов. В каждой строке сначала идёт тип запроса (1 или 2), за которым следуют необходимые параметры:- Для запроса типа 1: целое число
k(1 ≤ k ≤ n).
- Для запроса типа 2: целое число
p(1 ≤ p ≤ n) и значение (0 или 1), которое нужно установить по индексуp.
Выходные данные
Для каждого запроса типа 1 выведите индекс
k-го вхождения 1 в массиве. Если k-го вхождения не существует, выведите -1.Примеры
Входные данные | Выходные данные |
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