Folding XOR in Ranges

Hard

Take a non-empty block of numbers and *fold* it: at the same moment replace every number except the last with the XOR of itself and the number after it, then drop the last number. Repeat until one number is left; that number is the block's **fold result**. For example, [6, 3, 5] → [5, 6] → [3], so the result is 3. A block of one number folds to itself. You get an array values and a list of queries ranges, where ranges[i] = [l, r]. For each query, find the largest fold result over all contiguous blocks lying entirely inside values[l..r] (inclusive). Return the answers in query order.

Example 1

values=[6, 3, 5], ranges=[[0, 1], [0, 2], [2, 2]] → [6, 6, 5]

In range [0, 1] the blocks [6], [3] and [6, 3] give 6, 3 and 6 XOR 3 = 5, so the best is 6. The whole array [6, 3, 5] folds to [5, 6] and then to 3, while [3, 5] gives 6, so the best is again 6. Range [2, 2] is just the number 5.

Example 2

values=[1, 2, 4, 8], ranges=[[0, 3], [1, 2]] → [15, 6]

The whole array folds as [1, 2, 4, 8] → [3, 6, 12] → [5, 10] → [15], and 15 is the best result for the first query. In the second query the block [2, 4] gives 6.

Constraints

1 ≤ len(values) ≤ 2000
0 ≤ values[i] ≤ 2³¹ - 1
1 ≤ len(ranges) ≤ 10⁵
0 ≤ l ≤ r < len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming