会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
解题思路
我们要求序列的层级异或特征 C1,C2,…,Cn，其中 Ck 定义为所有长度为 k 的连续子段异或和的异或。直接对每个 k 重新计算所有子段异或和的复杂度为 O(n2)，无法通过 n≤2×105 的数据范围。我们需要利用异或的性质进行递推。
-
前缀异或和
构造前缀异或和数组 s，其中 s[i]=a1⊕a2⊕⋯⊕ai（规定 s[0]=0）。利用前缀异或和可以在 O(1) 时间内求出任意区间 [l,r] 的异或和：
X(l,r)=s[r]⊕s[l−1]
-
递推关系
