← 返回题目列表

Codeforces · 2117/H

H. 不断的雨

中文机器翻译题面 查看原题

注意异常的内存限制。

Silver Wolf 为您提供了一个长度为 $$$n$$$ 的数组 $$$a$$$ 和 $$$q$$$ 查询。在每个查询中,她都会替换 $$$a$$$ 中的一个元素。每次查询后,她都会要求您输出最大整数 $$$k$$$,以便存在一个整数 $$$x$$$,并且它是 $$$a$$$ 的子数组 $$$k$$$ 的多数。

如果 $$$y$$$ 在 $$$b$$$ 中出现至少 $$$\lfloor \frac{|b|+1}{2} \rfloor +k$$$ 次,则整数 $$$y$$$ 是数组 $$$b$$$ 的 $$$k$$$ 多数,其中 $$$|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$$$。

输出

对于每个测试用例,在一个新行上输出所有查询的答案,并用空格分隔。

示例

输入
复制

2
5 5
1 2 3 4 5
3 4
1 4
2 4
4 3
2 3
7 8
3 2 3 3 2 2 3
2 3
5 3
6 3
3 4
4 4
7 4
6 4
2 4

输出
复制

1 1 2 1 0 
2 2 3 2 1 1 1 2