PythonEveryDay

给出n个数字a1,a2,..an,问最多有多少个不重叠的非空区间，使得每个区间内的数字的xor值都等于0.
即找出最大的k，使得存在k个区间（l(i),r(i)），满足1<=l(i)<=r(i)<=n,1<=i<=k,r[i]<l(i+1),且
a[l(i)] xor a[l(i+1)] xor ... xor a[r(i)] = 0 (1<=i<=k)
输入描述：第一行一个整数n;第二行n个整数a1,a2,...an;
输出描述：一个整数，表示最多的区间个数

例子：输入
4
3 0 2 2
输出
2

0^A = A，表示任何数与0异或还是他自己。
动态规划，Si表示前i个数的异或值，S数列中存在相同的数就表示存在异或为0的子数组
比如a = [3, 0, 2, 2, 2, 0, 1, 2, 2]
s = [3 3 1 3 1 1 0 2 0]
s1 = s0,可知s1=0
s3 = s1,可知s2^s3=0
...
使用dp[i]表示前面i-1个数可以切分的最大区间，其中每个区间异或值都为0，
使用m记住dp[i]异或值为0的区间的最大索引，意味着后面的区间必须在m后面
则如果s[i]不在S[0:i]中,表示后面的区间没有异或为0的，dp[i+1] = dp[i]
如果s[i]在s[0:i]中，则表示后面区间有异或为0的，找到s[i]在s[0:i]的哪个位置，
如果该位置比m小，则dp[i+1] = dp[i]，该区间不算数，如果该位置大于等于m，该区间算数
dp[i+1] = dp[i]

可以用一个字典记录s中每个值出现的最大位置，每次更新最大值即可，不需要将s所有元素记录下来

a = [3, 0, 2, 2, 2, 0, 1, 2, 2]

s, m = 0, 0
dic = {0: 0}
dp = [0 for i in range(len(a)+1)]
for i in range(len(a)):
    s ^= a[i]
    if s not in dic:
        dic[s] = i + 1
        dp[i+1] = dp[i]
    else:
        if dic[s] >= m:
            dp[i+1] = dp[i] + 1
            m = dic[s]
        else:
            dp[i+1] = dp[i]

print(dp[-1])