java - 如何最佳地找到满足给定条件的数组的子集数？

Question

给定一个正整数数组，我们必须计算满足给定条件的所有子数组：X ^ 1 == X + 1，其中' ^ '是异或运算，X表示所有元素的异或那个子数组。

例子 ：

Say, A[n] = [1 2 2 4 5]
And we are given another array 
Queries[m] = [[1, 3], [2, 4]]
so for Queries[i] = [l, r] (l & r are array indices.)
and we have to count all the sub-arrays (for which X ^ 1 == X + 1) in subarray A[l:r] (both inclusive).

This operation we have to perform for each query and return solution for each query in result[] array.

So here, result[] = [6, 3].

说明：

result[0] = 6, as all 6 possible subarrays in range (2, 3) satisfies the condition,
similarly, result[1] = 3, as only subarray A[2:3], A[3:3] and A[2:3] satisfies the above condition

缺点：

N（数组大小）<= 2 x 10^5
M（查询数）<= 2 x 10^5

蛮力解决方案导致时间限制错误，因为根据约束，解决方案时间复杂度应 < O(n^2)。

如何最佳地解决这个问题？

标签： javac++algorithmdata-structuresbit-manipulation