Codeforces Global Round 13 |
---|
Закончено |
Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Изначально все элементы $$$a$$$ равны $$$0$$$ либо $$$1$$$. Вы должны обработать $$$q$$$ запросов двух типов:
Напомним, что $$$k$$$-й наибольший элемент массива $$$b$$$ определяется следующим образом:
Например, второй наибольший элемент массива $$$[0, 1, 0, 1]$$$ равен $$$1$$$, так как после сортировки в невозрастающем порядке он становится равен $$$[1, 1, 0, 0]$$$, а второй элемент в этом массиве равен $$$1$$$.
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — длину заданного массива и количество запросов.
Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$) — элементы исходного массива.
Каждая из следующих строк $$$q$$$ содержит два целых числа. Первое из них — $$$t$$$ ($$$1 \le t \le 2$$$) — тип запроса.
Гарантируется, что будет по крайней мере один запрос второго типа (удовлетворяющий $$$t = 2$$$).
Для каждого запроса второго типа выведите единственное целое число — ответ на запрос.
5 5 1 1 0 1 0 2 3 1 2 2 3 2 1 2 5
1 0 1 0
Изначально $$$a = [1, 1, 0, 1, 0]$$$.
В первой операции нужно вывести третье наибольшее значение, которое равно $$$1$$$.
Вторая операция присваивает $$$a_2$$$ значение $$$0$$$, $$$a$$$ становится $$$[1, 0, 0, 1, 0]$$$.
В третьей операции нужно вывести третье наибольшее значение, которое равно $$$0$$$.
В четвертой операции нужно вывести первое наибольшее значение, которое равно $$$1$$$.
В пятой операции нужно вывести пятое наибольшее значение, которое равно $$$0$$$.
Название |
---|