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.


-----Examples-----

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
Output
2
2
0
2
4
7
4


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

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Data structures

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	n = inp()
	arr = inlt()
	sor = 0
	ans = n
	st = set()
	for a in arr:
		sor ^= a
		if sor in st or sor == 0:
			ans -= 1
			st.clear()
			sor = 0
		st.add(sor)
	print(ans)
for _ in range(inp()):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	res = n
	for i in range(1, n):
		lst[i] ^= lst[i - 1]
	st = set()
	st.add(0)
	for i in lst:
		if i in st:
			res -= 1
			st.clear()
		st.add(i)
	print(res)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	for x in range(1, len(l)):
		l[x] = l[x] ^ l[x - 1]
	res = n
	s = set()
	s.add(0)
	for x in l:
		if x in s:
			res -= 1
			s = set()
		s.add(x)
	print(res)


xx = int(input())

def cal(n, arr):
	if n == 1:
		return 1 if arr[0] != 0 else 0
	t = 0
	s = -1
	ans = 0
	arr += [0]
	p = set()
	for i in range(n + 1):
		if arr[i] == 0:
			ans += i - s - 1
			s = i
			t = 0
			p = set()
			continue
		t = t ^ arr[i]
		if t == 0 or t in p:
			ans += i - s - 1
			s = i
			p = set()
			t = 0
		else:
			p.add(t)
	return ans
for jj in range(xx):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	print(cal(n, arr))


import heapq

def calc_nonzero(nums):
	cumsums = [0]
	cumsums_inds = {0: [0]}
	cur = 0
	for (i, x) in enumerate(nums, start=1):
		cur = cur ^ x
		if cur not in cumsums_inds:
			cumsums_inds[cur] = []
		cumsums_inds[cur].append(i)
		cumsums.append(cur)
	for (k, v) in cumsums_inds.items():
		heapq.heapify(v)
	max_counts = [0] * (len(nums) + 1)
	for (i, x) in enumerate(nums, start=1):
		max_counts[i] = max(max_counts[i], max_counts[i - 1])
		cs = cumsums[i - 1]
		if len(cumsums_inds[cs]) != 1:
			_me = heapq.heappop(cumsums_inds[cs])
			next_ind = cumsums_inds[cs][0]
			max_counts[next_ind] = max(max_counts[next_ind], max_counts[i - 1] + 1)
	return len(nums) - max_counts[-1]

def solve(nums):
	nums = nums + [0]
	res = 0
	cur = []
	for x in nums:
		if x == 0:
			if len(cur) > 0:
				res += calc_nonzero(cur)
			cur = []
		else:
			cur.append(x)
	return res
n = int(input())
for _ in range(n):
	input()
	nums = list(map(int, input().strip().split()))
	print(solve(nums))


import sys
input = sys.stdin.readline
from random import randint
RANDOM = randint(1, 10 ** 9)

class hf(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(hf, self).__hash__() ^ RANDOM

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	arr = readList()
	v = cnt = 0
	hv = {hf(v): -1}
	rb = -1
	for i in range(n):
		v = arr[i] ^ v
		val = hf(v)
		if val in hv and hv[val] >= rb:
			rb = i
			cnt += 1
		if val not in hv:
			hv[val] = 0
		hv[val] = i
	return n - cnt
for _ in range(int(input())):
	print(solve())