跳转至

3653. 区间乘法查询后的异或 I

题目描述

给你一个长度为 n 的整数数组 nums 和一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri, ki, vi]。

对于每个查询，按以下步骤执行操作：

  • 设定 idx = li。
  • 当 idx <= ri 时：
    • 更新：nums[idx] = (nums[idx] * vi) % (109 + 7)
    • 将 idx += ki。

在处理完所有查询后，返回数组 nums 中所有元素的 按位异或 结果。

 

示例 1：

输入： nums = [1,1,1], queries = [[0,2,1,4]]

输出： 4

解释：

  • 唯一的查询 [0, 2, 1, 4] 将下标 0 到下标 2 的每个元素乘以 4。
  • 数组从 [1, 1, 1] 变为 [4, 4, 4]。
  • 所有元素的异或为 4 ^ 4 ^ 4 = 4。

示例 2：

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

输出： 31

解释：

  • 第一个查询 [1, 4, 2, 3] 将下标 1 和 3 的元素乘以 3，数组变为 [2, 9, 1, 15, 4]。
  • 第二个查询 [0, 2, 1, 2] 将下标 0、1 和 2 的元素乘以 2，数组变为 [4, 18, 2, 15, 4]。
  • 所有元素的异或为 4 ^ 18 ^ 2 ^ 15 ^ 4 = 31。

 

提示：

  • 1 <= n == nums.length <= 103
  • 1 <= nums[i] <= 109
  • 1 <= q == queries.length <= 103
  • queries[i] = [li, ri, ki, vi]
  • 0 <= li <= ri < n
  • 1 <= ki <= n
  • 1 <= vi <= 105

解法

方法一：模拟

我们可以直接模拟题目中的操作，遍历每个查询并更新数组 \(\textit{nums}\) 中的对应元素。最后计算数组中所有元素的按位异或结果并返回。

时间复杂度 \(O(q \times \frac{n}{k})\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度，而 \(q\) 是查询的数量。空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        mod = 10**9 + 7
        for l, r, k, v in queries:
            for idx in range(l, r + 1, k):
                nums[idx] = nums[idx] * v % mod
        return reduce(xor, nums)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int xorAfterQueries(int[] nums, int[][] queries) {
        final int mod = (int) 1e9 + 7;
        for (var q : queries) {
            int l = q[0], r = q[1], k = q[2], v = q[3];
            for (int idx = l; idx <= r; idx += k) {
                nums[idx] = (int) (1L * nums[idx] * v % mod);
            }
        }
        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        const int mod = 1e9 + 7;
        for (const auto& q : queries) {
            int l = q[0], r = q[1], k = q[2], v = q[3];
            for (int idx = l; idx <= r; idx += k) {
                nums[idx] = 1LL * nums[idx] * v % mod;
            }
        }
        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func xorAfterQueries(nums []int, queries [][]int) int {
    const mod = int(1e9 + 7)
    for _, q := range queries {
        l, r, k, v := q[0], q[1], q[2], q[3]
        for idx := l; idx <= r; idx += k {
            nums[idx] = nums[idx] * v % mod
        }
    }
    ans := 0
    for _, x := range nums {
        ans ^= x
    }
    return ans
}

1
2
3
4
5
6
7
8
9
function xorAfterQueries(nums: number[], queries: number[][]): number {
    const mod = 1e9 + 7;
    for (const [l, r, k, v] of queries) {
        for (let idx = l; idx <= r; idx += k) {
            nums[idx] = (nums[idx] * v) % mod;
        }
    }
    return nums.reduce((acc, x) => acc ^ x, 0);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn xor_after_queries(mut nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
        let modv: i64 = 1_000_000_007;
        for q in queries {
            let (l, r, k, v) = (q[0] as usize, q[1] as usize, q[2] as usize, q[3] as i64);
            let mut idx = l;
            while idx <= r {
                nums[idx] = ((nums[idx] as i64 * v) % modv) as i32;
                idx += k;
            }
        }
        let mut ans = 0;
        for x in nums {
            ans ^= x;
        }
        return ans;
    }
}

评论