← 返回题目列表

Codeforces · 1718/A2

A2. 布伦卡与传统(硬版)

中文机器翻译题面 查看原题

这是这个问题的困难版本。简单版本和困难版本之间的区别仅在于 $$$a_i$$$ 和 $$$n$$$ 上的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

布伦卡是布里亚特的王储妃,很快她将成为该国第$$$n$$$女王。布里亚特有一个古老的传统——在加冕之前,统治者必须向居民展示他们的实力。为了确定第 $$$n$$$ 位统治者的实力,该国的居民给他们一个由 $$$a$$$ 组成的数组,其中恰好有 $$$n$$$ 个数字,之后统治者必须在最短的时间内将数组中的所有元素变成零。标尺可以多次执行以下两步操作:

- 选择两个索引 $$$l$$$ 和 $$$r$$$,使得 $$$1 \le l \le r \le n$$$ 和一个非负整数 $$$x$$$,然后
- 对于所有 $$$l \leq i \leq r$$$ 分配 $$$a_i := a_i \oplus x$$$,其中 $$$\oplus$$$ 表示按位异或运算。执行此操作需要 $$$\left\lceil \frac{r-l+1}{2} \right\rceil$$$ 秒,其中 $$$\lceil y \rceil$$$ 表示 $$$y$$$ 四舍五入到最接近的整数。

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

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 500)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 10^5)$$$ - 数组的大小

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \cdots , a_n$$$ $$$(0 \le a_i < 2^{30})$$$ — 数组的元素。

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

输出

对于每个测试用例,输出一个数字 - Burenka 需要的最短时间。

示例

输入 #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

注意

在第一个测试用例中,Burenka 可以选择段 $$$l = 1$$$、$$$r = 4$$$ 和 $$$x=5$$$。因此它将在 $$$2$$$ 秒内用零填充数组。

在第二个测试用例中,Burenka 首先选择段 $$$l = 1$$$、$$$r = 2$$$ 和 $$$x = 1$$$,然后 $$$a = [0, 2, 2]$$$,然后选择段 $$$l = 2$$$、$$$r = 3$$$ 和 $$$x=2$$$,其中用零填充数组。布伦卡总共将花费 $$$2$$$ 秒。