Maximum XOR Score Subarray Queries
You are given an array nums of n integers, and a 2D integer array queries of size q, where queries[i] = [li, ri].
For each query, you must find the maximum XOR score of any subarray of nums[li..ri].
The XOR score of an array a is found by repeatedly applying the following operations on a so that only one element remains; that element is the score:
- Simultaneously replace
a[i]witha[i] XOR a[i + 1]for all indicesiexcept the last one. - Remove the last element of
a.
Return an array answer of size q where answer[i] is the answer to query i.
Example 1
Input
nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]Output
[12,60,60]For the three queries, the largest XOR scores among subarrays of the requested ranges are 12, 60, and 60 respectively.
Example 2
Input
nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]Output
[7,14,11,14,5]For each query range, the maximum XOR score subarrays have scores 7, 14, 11, 14, and 5 respectively.
Constraints
- 1 <= n == nums.length <= 2000
- 0 <= nums[i] <= 2^31 - 1
- 1 <= q == queries.length <= 10^5
- queries[i].length == 2
- queries[i] = [li, ri]
- 0 <= li <= ri <= n - 1