CF1718A2 Burenka and Traditions (hard version)

这是本题的困难版本。简单版本与困难版本的区别仅在于 $a_i$ 和 $n$ 的约束条件。只有在两种版本都被解决的情况下，你才能进行 Hack。 Burenka 是布里亚特的王储公主，很快她将成为该国的第 $n$ 任女王。在布里亚特有一个古老的传统——加冕前，统治者必须向国民展示自己的力量。为了衡量第 $n$ 任统治者的力量，国民会给她一个长度恰好为 $n$ 的数组 $a$，之后统治者必须在最短时间内将数组的所有元素变为零。统治者可以进行如下的两步操作任意次： - 选择两个下标 $l$ 和 $r$，满足 $1 \le l \le r \le n$，以及一个非负整数 $x$，然后 - 对所有满足 $l \leq i \leq r$ 的 $i$，执行 $a_i := a_i \oplus x$，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。执行该操作需要 $\left\lceil \frac{r-l+1}{2} \right\rceil$ 秒，其中 $\lceil y \rceil$ 表示将 $y$ 向上取整。 请帮助 Burenka 计算她需要多少时间。

第一行包含一个整数 $t$ $(1 \le t \le 500)$，表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ $(1 \le n \le 10^5)$，表示数组的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ $(0 \le a_i < 2^{30})$，表示数组的元素。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示 Burenka 需要的最少时间。

在第一个测试用例中，Burenka 可以选择区间 $l=1$，$r=4$，$x=5$，这样可以在 $2$ 秒内将数组全部变为零。 在第二个测试用例中，Burenka 先选择区间 $l=1$，$r=2$，$x=1$，此时 $a=[0,2,2]$，然后选择区间 $l=2$，$r=3$，$x=2$，这样可以将数组全部变为零。Burenka 总共需要 $2$ 秒。 由 ChatGPT 4.1 翻译