algorithm - 三胞胎的数量

Question

我要找没有。 n 个元素数组中的三元组 (i,j,k) 使得子序列

Ai xor Ai+1 xor.......Aj-1 = Aj xor Aj+1 xor......Ak

在哪里

I<j<=k

这里，xor是按位异或

没有。数组中元素的个数最多为 10^5

我的方法:

我虽然想用蛮力，但肯定会失败

虽然我想从左侧和右侧滑动窗口，但这也会失败，因为它将是 O(n^2)

所以我想不出算法

任何人都可以提供提示吗？我不需要代码..只需要算法或小提示就可以了

Answer 1

对于所有对 (i,k)，其中 Ai xor Ai+1 xor ...... Ak = 0 任何 j (i < j <= k) 都可以。所以你只需要找到 xor 等于零的所有段。
要找到这些段，请计算前缀异或，然后对前缀异或及其位置进行排序。在排序的数组中找到具有相等异或的子数组(由于数组已排序，它们将排成一行)。您需要计算所有对之间的距离总和。
在此子数组中，元素按位置排序，因此每个段(相邻节点之间)将在此总和中使用 l * r 次，其中 l 是左元素之前的元素数，r 是右元素之后的元素数。所以你只需遍历你的子数组并使用相邻元素之间的距离之和乘以 l * r 来计算这个总和。这个算法是O(n log n)。