CF2049F.MEX OR Mania

我们称一个整数序列 $ b_1, b_2, \ldots, b_n $ 为「好的」，如果满足以下条件：$\operatorname{mex}(b_1, b_2, \ldots, b_n) - (b_1 | b_2 | \ldots | b_n) = 1$。这里，$\operatorname{mex(c)}$ 指的是集合 $c$ 中最小的未出现非负整数，而 $|$ 表示按位或运算。

Shohag 有一个整数序列 $ a_1, a_2, \ldots, a_n $。他会对序列 $a$ 进行 $q$ 次更新操作：

• 对于给定的 $i$ 和 $x$，将 $a_i$ 增加 $x$。

每次更新后，需要你帮他找出序列 $a$ 中最长的「好的」子数组长度。

输入包含多个测试用例。第一行是测试用例数量 $t$（1 ≤ $t$ ≤ 10,000）。每个测试用例包括以下内容：

• 第一行包含两个整数 $n$ 和 $q$（1 ≤ $n, q$ ≤ 100,000），分别表示序列的长度和更新操作的次数。
• 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（0 ≤ $a_i$ ≤ $n$）。
• 接下来的 $q$ 行中，每行描述一个更新操作：
  • 两个整数 $i$ 和 $x$（1 ≤ $i, x$ ≤ $n$），表示将 $a_i$ 增加 $x$。

保证所有测试用例中所有序列的元素个数之和不超过 100,000，所有更新操作的总数也不超过 100,000。

对于每个测试用例，输出 $q$ 行，每行是对应更新后序列中最长的「好的」子数组的长度。

例如，在第一个测试用例中，第一次更新后，数组变为 $[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]$。

本翻译由 AI 自动生成