不是的。三胞胎的

Question

我想找不到。在n个元素的阵列中的三元组(i，j，k)使得子序列

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

哪里

I<j<=k

在这里，xor是逐位xor。

不是的。数组中的元素数量最多可达10^5

我的方法是：

我想过使用暴力，但它肯定会失败。

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

所以我想不出算法

有没有人能给点提示？我不需要code..just算法，甚至是一些小提示都可以工作

Answer 1

对于所有的对(i，k)，其中任何j (i

为了找到这些段，计算前缀xor，然后对前缀xor及其位置对进行排序。在已排序数组中，查找具有相等异或的子数组(由于数组已排序，它们将在一行中)。你需要计算所有对之间的距离之和。

在这个子数组中，元素是按位置排序的，因此每个段(相邻节点之间)将在这个和中使用l*r次，其中l是左侧元素之前的元素数，r是右侧元素之后的元素数。所以你只需要遍历你的子数组，用相邻元素之间的距离之和乘以l* r来计算这个和。这个算法是O(n log n)。

Answer 2

如果一个三元组(i，j，k)是有效的，那么Ai xor Ai+1 xor ...xor Ak = 0。因此，如果你找到所有这样的对(i，k)，即Ai xor Ai+1 xor…你可以把j放在i和k之间的任何地方，你可以很容易地计算出三元组的数量。

为了在O(n log n)中找到这些对，你可以使用Trie数据结构，我相信它已经在包括Stack Overflow在内的许多网站上得到了很好的解释。