P9533 [YsOI2023] Interval Reversal and Interval XOR Sum

A data structure problem for Ysuperman template testdata. The name “符卡 (Fuka)” can be a person’s name or a team name.

Fuka has an integer array $a$ of length $n$. Fuka says an interval $[l,r]$ is a “spooky interval” if and only if $\bigoplus_{i=l}^r a_i = 0$, that is, the XOR of all numbers in this interval is exactly $0$. Fuka has special magic that can reverse **any** spooky interval. Specifically, if interval $[l,r]$ is a spooky interval, then Fuka can use magic on it, and the whole array becomes $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$. Now Fuka can use magic any number of times. She wants the final array to have as many spooky intervals as possible. Can you tell her what the maximum possible number of spooky intervals is?

The first line contains a positive integer $n$, the length of the array. The second line contains $n$ non-negative integers $a_1,a_2,\dots,a_n$, representing the entire array.

Output one line with one integer, the maximum possible number of spooky intervals after Fuka uses magic any number of times.

#### Explanation for Sample 1 No matter how many times Fuka uses magic, the array is always $1,1,1$, so using magic or not makes no difference. The spooky intervals are always exactly two: $[1,2]$ and $[2,3]$. #### Explanation for Sample 2 One possible way to use the magic is given here. Choose the spooky interval $[1,3]$ and use magic. The new array is $2,1,3,3$. This array has two spooky intervals: $[1,3]$ and $[3,4]$. It can be proven that the answer cannot exceed $2$. #### Constraints For the first $20\%$ of the data, $n \le 10$. For the first $40\%$ of the data, $n \le 2000$. Another $10\%$ of the data guarantees that all $a_i$ are equal. Another $10\%$ of the data guarantees that $a_i$ can take only two possible values. Another $10\%$ of the data guarantees that $0 \le a_i < 2^{10}$. For $100\%$ of the data, $1 \le n \le 10^5$ and $0 \le a_i < 2^{20}$. #### Easter Egg The name “spooky interval” is actually a pun on “zero XOR interval.” Translated by ChatGPT 5