Обратите внимание на необычное ограничение по памяти.
Серебряный Волк дает вам массив $$$a$$$ длиной $$$n$$$ и $$$q$$$ запросов. В каждом запросе она заменяет элемент в $$$a$$$. После каждого запроса она просит вас вывести максимальное целое число $$$k$$$, такое что существует целое число $$$x$$$, которое является $$$k$$$-большинством подмассива$$$^{\text{∗}}$$$ массива $$$a$$$.
Целое число $$$y$$$ является $$$k$$$-большинством массива $$$b$$$, если $$$y$$$ появляется как минимум $$$\lfloor \frac{|b|+1}{2} \rfloor +k$$$ раз в $$$b$$$, где $$$|b|$$$ представляет длину $$$b$$$. Обратите внимание, что $$$b$$$ может не иметь $$$k$$$-большинства.
$$$^{\text{∗}}$$$Массив $$$b$$$ является подмассивом массива $$$a$$$, если $$$b$$$ можно получить из $$$a$$$ путем удаления нескольких (возможно, нуля или всех) элементов с начала и нескольких (возможно, нуля или всех) элементов с конца.
Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 3 \cdot 10^5$$$) — длина $$$a$$$ и количество запросов.
Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ через пробел ($$$1 \leq a_i \leq n$$$).
Следующие $$$q$$$ строк содержат два целых числа $$$i$$$ и $$$x$$$, обозначающие запрос, который заменяет $$$a_i$$$ на $$$x$$$ ($$$1 \leq i, x \leq n$$$).
Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите ответ на все запросы в одной новой строке, разделенной пробелами.
25 51 2 3 4 53 41 42 44 32 37 83 2 3 3 2 2 32 35 36 33 44 47 46 42 4
1 1 2 1 0 2 2 3 2 1 1 1 2
| Codeforces Round 1029 (Div. 3) |
|---|
| Закончено |
