Hard

题目描述

给你一个正整数数组 nums 和一个正整数 k。你还会得到一个二维数组 queries，其中 queries[i] = [indexi, valuei, starti, xi]。

你可以对 nums 执行一次操作，即移除 nums 的任意后缀，使得 nums 保持非空。

对于给定的 x，数组 nums 的 x 值定义为执行此操作的方案数，使得剩余元素的乘积对 k 取模的余数等于 x。

对于 queries 中的每个查询，你需要在执行以下操作后确定 nums 对于 xi 的 x 值：

  1. 将 nums[indexi] 更新为 valuei。只有这一步会持续影响后续查询。
  2. 移除前缀 nums[0..(starti - 1)]（其中 nums[0..(-1)] 表示空前缀）。

返回一个大小为 queries.length 的数组 result，其中 result[i] 是第 i 个查询的答案。

数组的前缀是从数组开头开始并延伸到数组内任意位置的子数组。

数组的后缀是从数组内任意位置开始并延伸到数组末尾的子数组。

注意，操作中选择的前缀和后缀可以为空。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,1,2,1,1], k = 2, queries = [[2,1,0,1]]
输出：[5]

提示：

  • 1 <= nums[i] <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= k <= 5
  • 1 <= queries.length <= 2 * 10^4
  • queries[i] == [indexi, valuei, starti, xi]
  • 0 <= indexi <= nums.length - 1
  • 1 <= valuei <= 10^9
  • 0 <= starti <= nums.length - 1
  • 0 <= xi <= k - 1

解题思路

这道题要求我们高效地处理数组更新和区间查询操作。核心思路是使用线段树来维护前缀乘积的余数信息。

算法思路：

  1. 线段树设计：每个线段树节点存储一个长度为 k 的数组，记录该区间内所有前缀乘积对 k 取模的余数的出现次数。

  2. 节点合并：当合并两个子区间时，左子区间的每个前缀余数 left_mod 与右子区间的每个前缀余数 right_mod 组合，新的余数为 (left_mod * right_mod) % k。

  3. 查询处理：

    • 更新 nums[index] = value
    • 查询区间 [start, n-1] 的前缀乘积余数分布
    • 返回余数为 xi 的方案数

  4. 优化细节：由于 k ≤ 5，余数空间很小，可以高效地进行状态转移和合并操作。

时间复杂度主要来自线段树的构建和查询，每次查询的复杂度为 O(k² log n)，其中 k 很小，实际性能很好。

代码实现

class Solution {
public:
    vector<int> resultArray(vector<int>& nums, int k, vector<vector<int>>& queries) {
        int n = nums.size();
        
        // 线段树节点，存储每个余数的出现次数
        vector<vector<int>> tree(4 * n, vector<int>(k, 0));
        
        // 构建线段树
        function<void(int, int, int)> build = [&](int node, int start, int end) {
            if (start == end) {
                tree[node][nums[start] % k] = 1;
            } else {
                int mid = (start + end) / 2;
                build(2 * node, start, mid);
                build(2 * node + 1, mid + 1, end);
                
                // 合并左右子树
                for (int i = 0; i < k; i++) {
                    for (int j = 0; j < k; j++) {
                        tree[node][(i * j) % k] += tree[2 * node][i] * tree[2 * node + 1][j];
                    }
                }
            }
        };
        
        // 更新线段树
        function<void(int, int, int, int, int)> update = [&](int node, int start, int end, int idx, int val) {
            if (start == end) {
                fill(tree[node].begin(), tree[node].end(), 0);
                tree[node][val % k] = 1;
            } else {
                int mid = (start + end) / 2;
                if (idx <= mid) {
                    update(2 * node, start, mid, idx, val);
                } else {
                    update(2 * node + 1, mid + 1, end, idx, val);
                }
                
                // 重新合并
                fill(tree[node].begin(), tree[node].end(), 0);
                for (int i = 0; i < k; i++) {
                    for (int j = 0; j < k; j++) {
                        tree[node][(i * j) % k] += tree[2 * node][i] * tree[2 * node + 1][j];
                    }
                }
            }
        };
        
        // 查询线段树
        function<vector<int>(int, int, int, int, int)> query = [&](int node, int start, int end, int l, int r) -> vector<int> {
            if (r < start || end < l) {
                vector<int> result(k, 0);
                result[1] = 1;  // 空区间的乘积为1
                return result;
            }
            if (l <= start && end <= r) {
                return tree[node];
            }
            
            int mid = (start + end) / 2;
            vector<int> left_result = query(2 * node, start, mid, l, r);
            vector<int> right_result = query(2 * node + 1, mid + 1, end, l, r);
            
            vector<int> result(k, 0);
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    result[(i * j) % k] += left_result[i] * right_result[j];
                }
            }
            return result;
        };
        
        build(1, 0, n - 1);
        
        vector<int> result;
        for (auto& q : queries) {
            int index = q[0], value = q[1], start = q[2], x = q[3];
            
            // 更新数组
            update(1, 0, n - 1, index, value);
            
            // 查询区间 [start, n-1]
            vector<int> counts = query(1, 0, n - 1, start, n - 1);
            result.push_back(counts[x]);
        }
        
        return result;
    }
};

class Solution:
    def resultArray(self, nums: List[int], k: int, queries: List[List[int]]) -> List[int]:
        n = len(nums)
        
        # 线段树节点，存储每个余数的出现次数
        tree = [[0] * k for _ in range(4 * n)]
        
        def build(node, start, end):
            if start == end:
                tree[node][nums[start] % k] = 1
            else:
                mid = (start + end) // 2
                build(2 * node, start, mid)
                build(2 * node + 1, mid + 1, end)
                
                # 合并左右子树
                for i in range(k):
                    for j in range(k):
                        tree[node][(i * j) % k] += tree[2 * node][i] * tree[2 * node + 1][j]
        
        def update(node, start, end, idx, val):
            if start == end:
                tree[node] = [0] * k
                tree[node][val % k] = 1
            else:
                mid = (start + end) // 2
                if idx <= mid:
                    update(2 * node, start, mid, idx, val)
                else:
                    update(2 * node + 1, mid + 1, end, idx, val)
                
                # 重新合并
                tree[node] = [0] * k
                for i in range(k):
                    for j in range(k):
                        tree[node][(i * j) % k] += tree[2 * node][i] * tree[2 * node + 1][j]
        
        def query(node, start, end, l, r):
            if r < start or end < l:
                result = [0] * k
                result[1] = 1  # 空区间的乘积为1
                return result
            if l <= start and end <= r:
                return tree[node][:]
            
            mid = (start + end) // 2
            left_result = query(2 * node, start, mid, l, r)
            right_result = query(2 * node + 1, mid + 1, end, l, r)
            
            result = [0] * k
            for i in range(k):
                for j in range(k):
                    result[(i * j) % k] += left_result[i] * right_result[j]
            return result
        
        build(1, 0, n - 1)
        
        result = []
        for index, value, start, x in queries:
            # 更新数组
            update(1, 0, n - 1, index, value)
            
            # 查询区间 [start, n-1]
            counts = query(1, 0, n - 1, start, n - 1)
            result.append(counts[x])
        
        return result

public class Solution {
    public int[] ResultArray(int[] nums, int k, int[][] queries) {
        int n = nums.Length;
        
        // 线段树节点，存储每个余数的出现次数
        int[,] tree = new int[4 * n, k];
        
        void Build(int node, int start, int end) {
            if (start == end) {
                tree[node, nums[start] % k] = 1;
            } else {
                int mid = (start + end) / 2;
                Build(2 * node, start, mid);
                Build(2 * node + 1, mid + 1, end);
                
                // 合并左右子树
                for (int i = 0; i < k; i++) {
                    for (int j = 0; j < k; j++) {
                        tree[node, (i * j) % k] += tree[2 * node, i] * tree[2 * node + 1, j];
                    }
                }
            }
        }
        
        void Update(int node, int start, int end, int idx, int val) {
            if (start == end) {
                for (int i = 0; i < k; i++) {
                    tree[node, i] = 0;
                }
                tree[node, val % k] = 1;
            } else {
                int mid = (start + end) / 2;
                if (idx <= mid) {
                    Update(2 * node, start, mid, idx, val);
                } else {
                    Update(2 * node + 1, mid + 1, end, idx, val);
                }
                
                // 重新合并
                for (int i = 0; i < k; i++) {
                    tree[node, i] = 0;
                }
                for (int i = 0; i < k; i++) {
                    for (int j = 0; j < k; j++) {
                        tree[node, (i * j) % k] += tree[2 * node, i] * tree[2 * node + 1, j];
                    }
                }
            }
        }
        
        int[] Query(int node, int start, int end, int l, int r) {
            if (r < start || end < l) {
                int[] result = new int[k];
                result[1] = 1;  // 空区间的乘积为1
                return result;
            }
            if (l <= start && end <= r) {
                int[] result = new int[k];
                for (int i = 0; i < k; i++) {
                    result[i] = tree[node, i];
                }
                return result;
            }
            
            int mid = (start + end) / 2;
            int[] leftResult = Query(2 * node, start, mid, l, r);
            int[] rightResult = Query(2 * node + 1, mid + 1, end, l, r);
            
            int[] finalResult = new int[k];
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    finalResult[(i * j) % k] += leftResult[i] * rightResult[j];
                }
            }
            return finalResult;
        }
        
        Build(1, 0, n - 1);
        
        List<int> result = new List<int>();
        foreach (var q in queries) {
            int index = q[0], value = q[1], start = q[2], x = q[3];
            
            // 更新数组
            Update(1, 0, n - 1, index, value);
            
            // 查询区间 [start, n-1]
            int[] counts = Query(1, 0, n - 1, start, n - 1);
            result.Add(counts[x]);
        }
        
        return result.ToArray();
    }
}

var resultArray = function(nums, k, queries) {
    const result = [];
    
    for (const [index, value, start, x] of queries) {
        nums[index] = value;
        
        const subarray = nums.slice(start);
        let count = 0;
        
        for (let i = 0; i < subarray.length; i++) {
            let product = 1;
            for (let j = 0; j <= i; j++) {
                product = (product * subarray[j]) % k;
            }
            if (product === x) {
                count++;
            }
        }
        
        result.push(count);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目