当前位置: 代码迷 >> 综合 >> HYSBZ - 4260 Codechef REBXOR(前缀和求区间连续异或和,01字典树)
  详细解决方案

HYSBZ - 4260 Codechef REBXOR(前缀和求区间连续异或和,01字典树)

热度:57   发布时间:2023-12-09 20:13:19.0

链接:HYSBZ - 4260 Codechef REBXOR

题意:

在这里插入图片描述
其中 2 ≤ N ≤ 4 ? 1 0 5 2\le N\le4*10^5 2N4?105 0 ≤ A i ≤ 1 0 9 0\le A_i\le 10^9 0Ai?109


分析:

由于异或的性质: a ? a = 0 a\oplus a=0 a?a=0 0 ? a = a 0\oplus a=a 0?a=a

所以 连续区间的异或和 a [ L ] ? a [ L + 1 ] ? ? ? a [ R ] a[L]\oplus a[L+1]\oplus\cdots\oplus a[R] a[L]?a[L+1]???a[R]可以用前缀异或和(或后缀)的形式表示

如前缀异或和: p r e [ i ] pre[i] pre[i],表示 x o r j = 1 i a [ j ] xor_{j=1}^{i}a[j] xor