Burenka and Traditions (hard version)

1000ms

262144K

Description:

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. 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.

Input:

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$$$.

Output:

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

Sample Input:

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

Sample Output:

Note:

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.

Informação

Provedor Codeforces

Código CF1718A2