CF2247D2 XOR Sorting (Hard Version)

这是本题的 hard 版本。两个版本的唯一区别是在此版本中，$0 \le q \le 10^6$。 请注意，本题使用从零开始的下标。 对于由 $m$ 个正整数组成的数组 $b$，定义 $f(b)$ 如下： 对于一个非负整数 $k$，如果可以通过任意次执行如下操作将 $b$ 排序为非降序，则称 $b$ 可被 $k$-排序： 1. 选择两个下标 $i$ 和 $j$（$0 \le i < j \le m-1$），使得 $i \oplus j \le k$\footnote{$\oplus$ 表示[按位异或操作](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。}。请注意，条件是作用于下标 $i$ 和 $j$，而不是 $b_i$ 和 $b_j$ 的元素值。 2. 交换 $b_i$ 和 $b_j$ 的值。 $f(b)$ 的取值为最小的非负整数 $k$，使得数组 $b$ 可以被 $k$-排序。 现给定长度为 $n$ 的正整数数组 $a$，你需要对 $a$ 进行 $q$ 次更新。每次更新形式如下： - $i\;x$：将 $a_i$ 赋值为 $x$。 请注意，更新是持久的，也就是说，每次更新都会影响后续所有数组的状态。 对于每个 $a$ 的状态（初始状态以及每次更新后的状态，共 $q+1$ 次），请求出 $f(a)$ 的值。

每组测试数据包含多个测试用例。第一行输入测试用例的个数 $t$（$1 \le t \le 10^4$）。接下来依次输入各个测试用例。 每个测试用例第一行输入两个整数 $n$ 和 $q$（$1 \le n \le 10^6$，$0 \le q \le 10^6$），分别表示数组 $a$ 的长度和更新次数。 第二行输入 $n$ 个整数 $a_0, a_1, \ldots, a_{n-1}$（$1 \le a_i \le 10^9$），表示初始数组 $a$。 接下来 $q$ 行，每行输入两个整数 $i_j$ 和 $x_j$（$0 \le i_j < n$，$1 \le x_j \le 10^9$），表示第 $j$ 次更新：将 $a_{i_j}$ 赋值为 $x_j$。 保证所有测试用例中，$n$ 的和不超过 $10^6$。 保证所有测试用例中，$q$ 的和不超过 $10^6$。

对于每个测试用例，输出 $q + 1$ 个整数，分别表示数组的初始状态及每次更新后的 $f(a)$。

在第一个样例中，初始数组为 $a = [1,2]$。该数组本身已是有序的，所以 $f(a)=0$。 在第二个样例中，初始数组为 $a=[10^9, 10^9-1]$。可以交换 $a_0$ 和 $a_1$，将数组变为 $[10^9-1, 10^9]$，因此 $f(a) = 0 \oplus 1 = 1$。 唯一一次更新后，数组变为 $a=[10^9, 10^9]$。该数组已是有序的，因此 $f(a) = 0$。 在第三个样例中，初始数组 $a=[2,5,3,4,1,6]$。可以通过交换下标对 $(0,1)$ 及 $(0,4)$ 来调整，具体为 $[2,5,3,4,1,6] \to [5,2,3,4,1,6]$，再 $[5,2,3,4,1,6] \to [1,2,3,4,5,6]$。可以证明，不能用更小的 $k$ 实现排序，因此 $f(a)=\max(0\oplus 1, 0\oplus 4)=4$。 由 ChatGPT 5 翻译