Burenka and Traditions (hard version) (Codeforces 1718A2)
Tags: Greedy, data structures

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 copy
import random
import heapq
import math
import sys
import bisect
import datetime
from functools import lru_cache
from collections import deque
from collections import Counter
from collections import defaultdict
from itertools import combinations
from itertools import permutations
from types import GeneratorType
from functools import cmp_to_key
inf = float('inf')
sys.setrecursionlimit(10000000)

class FastIO:

    def __init__(self):
        return

    @staticmethod
    def _read():
        return sys.stdin.readline().strip()

    def read_int(self):
        return int(self._read())

    def read_float(self):
        return int(self._read())

    def read_ints(self):
        return map(int, self._read().split())

    def read_floats(self):
        return map(float, self._read().split())

    def read_ints_minus_one(self):
        return map(lambda x: int(x) - 1, self._read().split())

    def read_list_ints(self):
        return list(map(int, self._read().split()))

    def read_list_floats(self):
        return list(map(float, self._read().split()))

    def read_list_ints_minus_one(self):
        return list(map(lambda x: int(x) - 1, self._read().split()))

    def read_str(self):
        return self._read()

    def read_list_strs(self):
        return self._read().split()

    def read_list_str(self):
        return list(self._read())

    @staticmethod
    def st(x):
        return sys.stdout.write(str(x) + '\n')

    @staticmethod
    def lst(x):
        return sys.stdout.write(' '.join((str(w) for w in x)) + '\n')

    @staticmethod
    def round_5(f):
        res = int(f + 0.5)
        return res

    @staticmethod
    def bootstrap(f, stack=[]):

        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to
        return wrappedfunc

def main(ac=FastIO()):
    t = ac.read_int()
    for _ in range(t):
        n = ac.read_int()
        nums = ac.read_list_ints()
        pre = 0
        ans = n
        dct = {pre}
        for num in nums:
            if pre ^ num in dct:
                ans -= 1
                dct = {pre}
            else:
                pre ^= num
                dct.add(pre)
        ac.st(ans)
    return
main()

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)