← 返回题目列表

Codeforces · 2049/F

F. 墨西哥或狂热

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

如果 $$$\operatorname{mex}(b_1, b_2, \ldots, b_n) - (b_1 | b_2 | \dots | b_n) = 1$$$,则整数序列 $$$b_1, b_2, \ldots, b_n$$$ 是好的。这里,$$$\operatorname{mex(c)}$$$表示集合$$$c$$$的MEX$$$^{\text{*}}$$$,$$$|$$$是按位OR运算符。

Shohag 有一个整数序列 $$$a_1, a_2, \ldots, a_n$$$。他将对 $$$a$$$ 执行以下 $$$q$$$ 更新:

- $$$i$$$ $$$x$$$ — 将 $$$a_i$$$ 增加 $$$x$$$。

每次更新后,帮他求$$$a$$$的最长的好子数组$$$^{\text{†}}$$$的长度。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$)。

每个测试用例接下来的 $$$q$$$ 行具有以下形式:

- $$$i$$$ $$$x$$$ ($$$1 \le i, x \le n$$$) - 这意味着您应该将 $$$a_i$$$ 增加 $$$x$$$。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$,并且$$$q$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出 $$$q$$$ 行 - 在第 $$$i$$$ 行上输出第 $$$i$$$ 更新后 $$$a$$$ 的最长好子数组的长度。

示例

输入 #1

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

输出 #1

6
3
2
0

注意

在第一个测试用例中,第一次更新后,数组变成 $$$[0, 0, 1, 0, 1, 1]$$$,这里整个数组都很好,因为 $$$\operatorname{mex}([0, 0, 1, 0, 1, 1]) - (0 | 0 | 1 | 0 | 1 | 1) = 2 - 1 = 1$$$。

第二次更新后,数组变成$$$[0, 0, 3, 0, 1, 1]$$$,这里子数组$$$[0, 1, 1]$$$是所有好的子数组中长度最大的。

最后,第三次更新后,数组变为$$$[0, 0, 3, 0, 1, 4]$$$,这里子数组$$$[0, 0]$$$和$$$[0, 1]$$$都是所有好的子数组中长度最大的。