MEX OR Mania
Contest: Codeforces Round 994 (Div. 2)
Difficulty rating: 2700
Tags: bitmasks, brute force, data structures, dsu, implementation

An integer sequence $$$b_1, b_2, \ldots, b_n$$$ is good if $$$\operatorname{mex}(b_1, b_2, \ldots, b_n) - (b_1 | b_2 | \ldots | b_n) = 1$$$. Here, $$$\operatorname{mex(c)}$$$ denotes the MEX$$$^{\text{∗}}$$$ of the collection $$$c$$$, and $$$|$$$ is the bitwise OR operator.

Shohag has an integer sequence $$$a_1, a_2, \ldots, a_n$$$. He will perform the following $$$q$$$ updates on $$$a$$$:

- $$$i$$$ $$$x$$$ — increase $$$a_i$$$ by $$$x$$$.

After each update, help him find the length of the longest good subarray$$$^{\text{†}}$$$ of $$$a$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

The next $$$q$$$ lines of each test case are of the following form:

- $$$i$$$ $$$x$$$ ($$$1 \le i, x \le n$$$) — it means you should increase $$$a_i$$$ by $$$x$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$ and the sum of $$$q$$$ doesn't exceed $$$10^5$$$.

Output format:
For each test case, output $$$q$$$ lines — on the $$$i$$$-th line output the length of the longest good subarray of $$$a$$$ after the $$$i$$$-th update.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Note:
In the first test case, after the first update, the array becomes $$$[0, 0, 1, 0, 1, 1]$$$, and here the whole array is good because $$$\operatorname{mex}([0, 0, 1, 0, 1, 1]) - (0 | 0 | 1 | 0 | 1 | 1) = 2 - 1 = 1$$$.

After the second update, the array becomes $$$[0, 0, 3, 0, 1, 1]$$$, and here the subarray $$$[0, 1, 1]$$$ has the maximum length among all the good subarrays.

Finally, after the third update, the array becomes $$$[0, 0, 3, 0, 1, 4]$$$, and here the subarrays $$$[0, 0]$$$ and $$$[0, 1]$$$ both have the maximum length among all the good subarrays.

Example input:
2
6 3
0 0 1 0 1 0
6 1
3 2
6 3
3 1
1 3 1
1 1

Example output:
6
3
2
0

Editorial:
Let's figure out when a sequence is good. Let $$$m$$$ be the maximum element of the sequence. Notice that the bitwise OR of the sequence is at least $$$m$$$ and as MEX $$$-$$$ OR $$$=1$$$, that means MEX has to be at least $$$m + 1$$$. Which means all elements from $$$0$$$ to $$$m$$$ has to be present in the sequence. As MEX can't be greater than $$$m + 1$$$, the MEX has to be exactly $$$m + 1$$$.
Now we need to check for which $$$m$$$ the bitwise OR of the elements from $$$0$$$ to $$$m$$$ is exactly $$$m$$$. It's not hard to see that this is true for $$$m = 2^k - 1$$$ for some integer $$$k \geq 0$$$. The reason is that all bits from $$$0$$$ to $$$k - 1$$$ have to be set in $$$m$$$ for the OR to be $$$m$$$ and it's only possible if $$$m$$$ is of the form $$$2^k - 1$$$.
So, a sequence is good if the maximum element is $$$m = 2^k - 1$$$ for some integer $$$k$$$ and all elements from $$$0$$$ to $$$m$$$ are present in the sequence.
Now, let's see how to answer the queries without any updates. To find the longest good subarray, we can use a two-pointers approach. But a better way to do this is to fix the power $$$k (0 \leq k \leq \log_2 n)$$$ and find the longest good subarray with maximum element $$$2^k - 1$$$. To do this, ignore the elements greater than $$$2^k - 1$$$ and then split the array into segments of consecutive numbers where each segment has elements from $$$0$$$ to $$$2^k - 1$$$. To check if a segment is good, we can track the number of distinct elements in the segment. If the number of distinct elements is $$$2^k$$$, then the segment is good.
So to sum it up, for each power $$$k$$$, we will track some segments/components and the number of distinct elements in them and also the lengths of the segments to get the longest one during queries.
Now regarding the updates, it is hard to track everything if we do the updates normally. But its's easier if we look at them in reverse order!
Then each update will be decreasing the value of $$$a_i$$$ by $$$x$$$. Then for each power $$$k$$$, we will have to add a new element to a component or merge two components. For tracking distinct elements, we can use a map or unordered map and to merge we can use DSU with small to large merging. And that's pretty much it.
Please check my code for more details.
Overall complexity is $$$O((n + q) \log^2 n)$$$ or $$$O((n + q) \log^3 n)$$$ depending on if you use an unordered map or a map.