版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [BZOJ 5301] [LOJ 2534] [Luogu P4462] [CQOI2018] 异或序列" categories:
一句话题意: 查询区间内子区间异或和为一定值的个数
暴力: $O(n^3m)$ (查询:$O(m)$, 枚举子序列: $O(n^2)$, 计算异或和: $O(n)$)
优化:
$\Rightarrow O(n^2m)$: 前缀和 (计算异或和: $O(n)\Rightarrow O(1)$)
令
$$ si:=\bigoplus{i=1}^x a_i $$
则
$$ \bigoplus_{i=l}^r ai=s{l-1}\oplus s_r $$
$\Rightarrow O(nm)$: 莫队
转换思路
注意到
$$ a\oplus b=c\iff a\oplus c=b $$
用一个桶cnt[x]记录当前区间内s[i]=x的个数
则当前区间的结果为 $\displaystyle\sum{i=l}^r\mathrm{cnt}{s_i\oplus k}$
$\Rightarrow O(n\min{m,\sqrt n})$: 奇偶化排序优化