Burenka and Traditions (hard version)

题意翻译

有 $T$ 组数据，对于每一组数据，你有一个长度为 $n$ 的数组 $a$，每一次操作可以选择一段区间 $[l,r]$，花费 $\left \lceil \dfrac{r-l+1}{2} \right \rceil$ 秒使区间内的数都异或 $x$，问最少需要几秒才能把数组中所有的元素都变成零。

题目描述

This is the hard version of this problem. The difference between easy and hard versions is only the constraints on $ a_i $ and on $ n $ . You can make hacks only if both versions of the problem are solved. Burenka is the crown princess of Buryatia, and soon she will become the $ n $ -th queen of the country. There is an ancient tradition in Buryatia — before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the $ n $ -th ruler, the inhabitants of the country give them an array of $ a $ of exactly $ n $ numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times: - select two indices $ l $ and $ r $ , so that $ 1 \le l \le r \le n $ and a non-negative integer $ x $ , then - for all $ l \leq i \leq r $ assign $ a_i := a_i \oplus x $ , where $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). It takes $ \left\lceil \frac{r-l+1}{2} \right\rceil $ seconds to do this operation, where $ \lceil y \rceil $ denotes $ y $ rounded up to the nearest integer. Help Burenka calculate how much time she will need.

输入输出格式

输入格式

The first line contains a single integer $ t $ $ (1 \le t \le 500) $ — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ $ (1 \le n \le 10^5) $ - the size of the array The second line of each test case contains $ n $ integers $ a_1, a_2, \cdots , a_n $ $ (0 \le a_i < 2^{30}) $ — elements of the array. It is guaranteed that the sum of $ n $ in all tests does not exceed $ 10^5 $ .

输出格式

For each test case, output a single number — the minimum time that Burenka will need.

输入输出样例

输入样例 #1

7
4
5 5 5 5
3
1 3 2
2
0 0
3
2 5 7
6
1 2 3 3 2 1
10
27 27 34 32 2 31 23 56 52 4
5
1822 1799 57 23 55

输出样例 #1

2
2
0
2
4
7
4

说明

In the first test case, Burenka can choose segment $ l = 1 $ , $ r = 4 $ , and $ x=5 $ . so it will fill the array with zeros in $ 2 $ seconds. In the second test case, Burenka first selects segment $ l = 1 $ , $ r = 2 $ , and $ x = 1 $ , after which $ a = [0, 2, 2] $ , and then the segment $ l = 2 $ , $ r = 3 $ , and $ x=2 $ , which fills the array with zeros. In total, Burenka will spend $ 2 $ seconds.

**题目大意：**
布伦卡是布里亚特王国的王储，很快她将成为这个国家的第n位女王。布里亚特有一个古老的传统，在加冕之前，统治者必须向居民展示他们的力量。为了确定第n位统治者的力量，居民会给他们一个包含n个数字的数组a，统治者必须以最短的时间将数组的所有元素变成零。统治者可以进行以下两步操作任意次：

- 选择两个索引l和r，使得1≤l≤r≤n，以及一个非负整数x，
- 对于所有l≤i≤r，赋值ai:=ai⊕x，其中⊕表示按位异或操作。这个操作需要⌈(r−l+1)/2⌉秒，其中⌈y⌉表示y向上取整到最近的整数。

帮助布伦卡计算她需要多少时间。

**输入输出数据格式：**
**输入格式：**
第一行包含一个整数t(1≤t≤500)——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数n(1≤n≤10^5)——数组的大小。

每个测试用例的第二行包含n个整数a1,a2,⋯,an(0≤ai<2^30)——数组的元素。

保证所有测试中n的总和不超过10^5。

**输出格式：**
对于每个测试用例，输出一个数字——布伦卡将需要的最少时间。**题目大意：** 布伦卡是布里亚特王国的王储，很快她将成为这个国家的第n位女王。布里亚特有一个古老的传统，在加冕之前，统治者必须向居民展示他们的力量。为了确定第n位统治者的力量，居民会给他们一个包含n个数字的数组a，统治者必须以最短的时间将数组的所有元素变成零。统治者可以进行以下两步操作任意次： - 选择两个索引l和r，使得1≤l≤r≤n，以及一个非负整数x， - 对于所有l≤i≤r，赋值ai:=ai⊕x，其中⊕表示按位异或操作。这个操作需要⌈(r−l+1)/2⌉秒，其中⌈y⌉表示y向上取整到最近的整数。 帮助布伦卡计算她需要多少时间。 **输入输出数据格式：** **输入格式：** 第一行包含一个整数t(1≤t≤500)——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n(1≤n≤10^5)——数组的大小。 每个测试用例的第二行包含n个整数a1,a2,⋯,an(0≤ai<2^30)——数组的元素。 保证所有测试中n的总和不超过10^5。 **输出格式：** 对于每个测试用例，输出一个数字——布伦卡将需要的最少时间。