3277. 查询子数组最大异或值

给你一个由 n 个整数组成的数组 nums，以及一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri]。

对于每一个查询，你需要找出 nums[li..ri] 中任意

子数组

的 最大异或值。

数组的异或值 需要对数组 a 反复执行以下操作，直到只剩一个元素，剩下的那个元素就是 异或值：

  • 对于除最后一个下标以外的所有下标 i，同时将 a[i] 替换为 a[i] XOR a[i + 1] 。
  • 移除数组的最后一个元素。

返回一个大小为 q 的数组 answer，其中 answer[i] 表示查询 i 的答案。

示例 1：

输入： nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]

输出： [12,60,60]

解释：

在第一个查询中，nums[0..2] 的子数组分别是 [2], [8], [4], [2, 8], [8, 4], 和 [2, 8, 4]，它们的异或值分别为 2, 8, 4, 10, 12, 和 6。查询的答案是 12，所有异或值中的最大值。

在第二个查询中，nums[1..4] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值，为 60。

在第三个查询中，nums[0..5] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值，为 60。

示例 2：

输入： nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]

输出： [7,14,11,14,5]

提示：

  • 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

区间dp套区间dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[] maximumSubarrayXor(int[] nums, int[][] queries) {
        // [a, b, c, d, e, f]
        // [a^b, b^c, c^d, d^e, e^f]            
        // [a^b2^c, b^c2^d, c^d2^e, d^e2^f]     [a^c, b^d, c^e]
        // [a^b3^c3^d, b^c3^d3^e, c^d3^e3^f]    [a^b^c^d, b^c^d^e]
        // [a^b4^c6^d4^e, b^c4^d6^e4^f]         [a^e, b^f]
        // [a^b5^c10^d10^e5^f]                  [a^b^e^f]

        int n = nums.length, m = queries.length;
        // xor[i][j]: 对于数组nums[i:j]的异或结果
        // xor[i][j] = xor[i][j-1] ^ xor[i+1][j] !!!
        int xor[][] = new int[n][n];
        // f[i][j]: nums[i-j]任意子数组的最大异或值
        // f[i][j] = max(f[i][j-1], f[i+1][j]) !!!
        int f[][] = new int[n+1][n+1];
        for (int i = n-1; i >= 0; i--) {
            xor[i][i] = nums[i];
            f[i][i] = nums[i];
            for (int j = i+1; j < n; j++) {
                xor[i][j] = xor[i][j-1] ^ xor[i+1][j];
                f[i][j] = Math.max(xor[i][j], Math.max(f[i][j-1], f[i+1][j]));
            }
        }
        int res[] = new int[m];
        for (int i = 0; i < m; i++) {
            int q[] = queries[i], x = q[0], y = q[1];
            res[i] = f[x][y];
        }
        return res;
    }
}