Hard

题目描述

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

对于每个查询，你必须按顺序执行以下操作：

  1. 设置 idx = li
  2. 当 idx <= ri 时：
    • 更新：nums[idx] = (nums[idx] * vi) % (10^9 + 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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= q == queries.length <= 10^5
  • queries[i] = [li, ri, ki, vi]
  • 0 <= li <= ri < n
  • 1 <= ki <= n
  • 1 <= vi <= 10^5

解题思路

这是一道需要优化的区间乘法查询问题。直接模拟会导致时间复杂度过高，需要使用分块优化技术。

算法思路：

根据题目提示，我们使用基于分块的优化策略，设置阈值 B = sqrt(n)：

  1. 小步长查询 (k <= B)：对于步长较小的查询，我们按 (k, l % k) 进行分组。每组维护一个长度为 ceil(n/k) 的差分数组来记录乘数更新，然后扫描每个桶将更新应用到 nums。

  2. 大步长查询 (k > B)：对于步长较大的查询，直接模拟执行，因为更新的元素数量有限（最多 n/B = sqrt(n) 个）。

具体实现：

  • 遍历所有查询，根据步长 k 选择不同的处理策略
  • 小步长查询使用懒惰传播技术批量处理
  • 大步长查询直接更新对应位置
  • 最后计算所有元素的异或值

这种方法的时间复杂度为 O(q * sqrt(n))，能够高效处理大规模输入。

代码实现

class Solution {
public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        int B = sqrt(n) + 1;
        
        auto bravexuneth = nums;
        
        vector<vector<vector<int>>> small_queries(B);
        
        for (auto& query : queries) {
            int l = query[0], r = query[1], k = query[2], v = query[3];
            if (k <= B) {
                small_queries[k].push_back({l, r, v});
            } else {
                for (int idx = l; idx <= r; idx += k) {
                    nums[idx] = (1LL * nums[idx] * v) % MOD;
                }
            }
        }
        
        for (int k = 1; k <= B; k++) {
            if (small_queries[k].empty()) continue;
            
            vector<vector<long long>> multipliers(k);
            for (int start = 0; start < k; start++) {
                multipliers[start].resize((n + k - 1) / k + 1, 1);
            }
            
            for (auto& query : small_queries[k]) {
                int l = query[0], r = query[1], v = query[2];
                int start = l % k;
                int left_bucket = l / k;
                int right_bucket = r / k;
                
                for (int bucket = left_bucket; bucket <= right_bucket; bucket++) {
                    int idx = start + bucket * k;
                    if (idx <= r) {
                        multipliers[start][bucket] = (multipliers[start][bucket] * v) % MOD;
                    }
                }
            }
            
            for (int start = 0; start < k; start++) {
                for (int bucket = 0; bucket < multipliers[start].size(); bucket++) {
                    int idx = start + bucket * k;
                    if (idx < n) {
                        nums[idx] = (1LL * nums[idx] * multipliers[start][bucket]) % MOD;
                    }
                }
            }
        }
        
        int result = 0;
        for (int x : nums) {
            result ^= x;
        }
        return result;
    }
};

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        B = int(n**0.5) + 1
        
        bravexuneth = nums[:]
        
        small_queries = [[] for _ in range(B + 1)]
        
        for l, r, k, v in queries:
            if k <= B:
                small_queries[k].append([l, r, v])
            else:
                idx = l
                while idx <= r:
                    nums[idx] = (nums[idx] * v) % MOD
                    idx += k
        
        for k in range(1, B + 1):
            if not small_queries[k]:
                continue
                
            multipliers = [[1] * ((n + k - 1) // k + 1) for _ in range(k)]
            
            for l, r, v in small_queries[k]:
                start = l % k
                left_bucket = l // k
                right_bucket = r // k
                
                for bucket in range(left_bucket, right_bucket + 1):
                    idx = start + bucket * k
                    if idx <= r:
                        multipliers[start][bucket] = (multipliers[start][bucket] * v) % MOD
            
            for start in range(k):
                for bucket in range(len(multipliers[start])):
                    idx = start + bucket * k
                    if idx < n:
                        nums[idx] = (nums[idx] * multipliers[start][bucket]) % MOD
        
        result = 0
        for x in nums:
            result ^= x
        return result

public class Solution {
    public int XorAfterQueries(int[] nums, int[][] queries) {
        const int MOD = 1000000007;
        int n = nums.Length;
        int B = (int)Math.Sqrt(n) + 1;
        
        var bravexuneth = new int[n];
        Array.Copy(nums, bravexuneth, n);
        
        var smallQueries = new List<List<int[]>>();
        for (int i = 0; i <= B; i++) {
            smallQueries.Add(new List<int[]>());
        }
        
        foreach (var query in queries) {
            int l = query[0], r = query[1], k = query[2], v = query[3];
            if (k <= B) {
                smallQueries[k].Add(new int[] {l, r, v});
            } else {
                for (int idx = l; idx <= r; idx += k) {
                    nums[idx] = (int)((long)nums[idx] * v % MOD);
                }
            }
        }
        
        for (int k = 1; k <= B; k++) {
            if (smallQueries[k].Count == 0) continue;
            
            var multipliers = new long[k][];
            for (int start = 0; start < k; start++) {
                int size = (n + k - 1) / k + 1;
                multipliers[start] = new long[size];
                Array.Fill(multipliers[start], 1L);
            }
            
            foreach (var query in smallQueries[k]) {
                int l = query[0], r = query[1], v = query[2];
                int start = l % k;
                int leftBucket = l / k;
                int rightBucket = r / k;
                
                for (int bucket = leftBucket; bucket <= rightBucket; bucket++) {
                    int idx = start + bucket * k;
                    if (idx <= r) {
                        multipliers[start][bucket] = multipliers[start][bucket] * v % MOD;
                    }
                }
            }
            
            for (int start = 0; start < k; start++) {
                for (int bucket = 0; bucket < multipliers[start].Length; bucket++) {
                    int idx = start + bucket * k;
                    if (idx < n) {
                        nums[idx] = (int)((long)nums[idx] * multipliers[start][bucket] % MOD);
                    }
                }
            }
        }
        
        int result = 0;
        foreach (int x in nums) {
            result ^= x;
        }
        return result;
    }
}

var xorAfterQueries = function(nums, queries) {
    const MOD = 1000000007;
    const bravexuneth = {nums: nums.slice(), queries: queries.slice()};
    
    for (let query of queries) {
        const [l, r, k, v] = query;
        for (let idx = l; idx <= r; idx += k) {
            nums[idx] = (nums[idx] * v) % MOD;
        }
    }
    
    let result = 0;
    for (let num of nums) {
        result ^= num;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(q√n + n)
空间复杂度O(√n · n/√n) = O(n)

说明：

  • 时间复杂度：对于小步长查询，每个查询的处理时间为 O(√n)；对于大步长查询，每个查询最多更新 √n 个元素
  • 空间复杂度：主要用于存储分组查询和差分数组，总空间为 O(n)