Burenka and Traditions (hard version) (Codeforces 1719D2)
Tags: Greedy, bitmasks

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

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.

Sample Inputs:
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 Outputs:
2
2
0
2
4
7
4

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)