CF2247D2 XOR Sorting (Hard Version)

This is the hard version of the problem. The only difference between the versions is that in this version, $ 0 \le q \le 10^6 $ . Note that zero-based indexing is used in this problem. For an array $ b $ consisting of $ m $ positive integers, define $ f(b) $ as follows. For a non-negative integer $ k $ , we say that $ b $ can be $ k $ -sorted if it can be sorted in non-decreasing order by performing the following operation any number of times: 1. Choose two indices $ i $ and $ j $ ( $ 0 \le i \lt j \le m - 1 $ ) such that $ i \oplus j \le k $ $ ^{\text{∗}} $ . Note that the condition applies to the indices $ i $ and $ j $ , not to the elements $ b_i $ and $ b_j $ . 2. Swap the elements $ b_i $ and $ b_j $ . The value $ f(b) $ is defined as the smallest non-negative integer $ k $ such that the array $ b $ can be $ k $ -sorted. You are given an array $ a $ of length $ n $ , consisting of positive integers. You will perform $ q $ updates on $ a $ . Each update has the following form: - $ i \; x $ : assign $ a_i = x $ . Note that the updates are persistent. In other words, each update affects all subsequent states of the array. For each of the $ q + 1 $ states of $ a $ — the initial state and the state after each of the $ q $ updates — find the value of $ f(a) $ . $ ^{\text{∗}} $ $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)

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 integers $ n $ and $ q $ ( $ 1 \le n \le 10^6 $ , $ 0 \le q \le 10^6 $ ) — the length of the array $ a $ and the number of updates. The second line of each test case contains $ n $ integers $ a_0, a_1, \ldots, a_{n - 1} $ ( $ 1 \le a_i \le 10^9 $ ) — the array $ a $ . The $ j $ -th of the following $ q $ lines contains two integers $ i_j $ and $ x_j $ ( $ 0 \le i_j \lt n $ , $ 1 \le x_j \le 10^9 $ ) — the description of the $ j $ -th update. This update means that the assignment $ a_{i_j} = x_j $ is performed. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ . It is guaranteed that the sum of $ q $ over all test cases does not exceed $ 10^6 $ .

For each test case, output $ q + 1 $ integers — the values of $ f(a) $ for the initial state of the array and after each of the $ q $ updates, in order.

In the first example, the initial array is $ a = [1, 2] $ . It is already sorted, so $ f(a) = 0 $ . In the second example, the initial array is $ a = [10^9, 10^9 - 1] $ . We can swap $ a_0 $ and $ a_1 $ , transforming $ a $ as follows: $ [\color{red}{10^9}, \color{red}{10^9 - 1}] \rightarrow [\color{red}{10^9 - 1}, \color{red}{10^9}] $ . Therefore, $ f(a) = 0 \oplus 1 = 1 $ . After the only update, the array becomes $ a = [10^9, 10^9] $ . It is already sorted, so $ f(a) = 0 $ . In the third example, the initial array is $ a = [2, 5, 3, 4, 1, 6] $ . We can perform swaps using the index pairs $ (0, 1) $ and $ (0, 4) $ , transforming $ a $ as follows: $ [\color{red}{2}, \color{red}{5}, 3, 4, 1, 6] \rightarrow [\color{red}{5}, \color{red}{2}, 3, 4, 1, 6] $ , $ [\color{red}{5}, 2, 3, 4, \color{red}{1}, 6] \rightarrow [\color{red}{1}, 2, 3, 4, \color{red}{5}, 6] $ . It can be shown that no smaller value of $ k $ is sufficient, so $ f(a) = \max(0 \oplus 1, 0 \oplus 4) = 4 $ .