[YsOI2023] 区间翻转区间异或和

题目背景

Ysuperman 模板测试的数据结构题。 符卡可以是人名也可以是队名。

题目描述

符卡有一个长度为 $n$ 的整数数组 $a$,符卡认为一个区间 $[l,r]$ 是灵异区间当且仅当 $\bigoplus_{i=l}^ra_i=0$,或者说这个区间内所有数字异或起来刚好等于 $0$。 符卡有特殊的魔法,可以把**任意**一个灵异区间翻转。具体来说,如果 $[l,r]$ 区间是灵异区间,那么符卡就可以对这个区间使用魔法,整个数组就会变成 $a_1,a_2,\dots,a_{l-1},a_r,a_{r-1},\dots,a_l,a_{r+1},a_{r+2}\dots,a_n$。 现在符卡可以使用任意次数的魔法,符卡希望最后得到的数组的灵异区间数量能够尽可能多,你能告诉她最后最多有多少个灵异区间吗?

输入输出格式

输入格式


第一行一个正整数 $n$,表示数组长度。 第二行 $n$ 个非负整数 $a_1,a_2,\dots,a_n$ 表示整个数组。

输出格式


输出一行一个整数,表示符卡使用任意次魔法后灵异区间最多有多少个。

输入输出样例

输入样例 #1

3
1 1 1

输出样例 #1

2

输入样例 #2

4
3 1 2 3

输出样例 #2

2

说明

#### 样例 1 解释 无论符卡发动多少次魔法,数组都是 $1,1,1$,所以发不发动魔法都没有任何关系。灵异区间永远都是 $[1,2],[2,3]$ 两个。 #### 样例 2 解释 这里给出可能的一种魔法发动方法。 选择灵异区间 $[1,3]$ 发动魔法,得到的新数组是 $2,1,3,3$,这个数组共有两个灵异区间,分别是 $[1,3]$ 和 $[3,4]$。 可以证明答案无法超过 $2$。 #### 数据范围 对于前 $20\%$ 的数据,保证 $n\le 10$。 对于前 $40\%$ 的数据,保证 $n\le 2000$。 另有 $10\%$ 的数据,保证 $a_i$ 全部相等。 另有 $10\%$ 的数据,保证 $a_i$ 只有两种可能的取值。 另有 $10\%$ 的数据,保证 $0\le a_i<2^{10}$。 对于 $100\%$ 的数据,满足 $1\le n\le 10^5$,$0\le a_i< 2^{20}$。 #### 彩蛋 灵异区间的名字其实是“零异(或)区间”的谐音。