标签： hard

3093.最长公共后缀查询

目标

给你两个字符串数组 wordsContainer 和 wordsQuery 。

对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有 最长公共后缀 的字符串。如果 wordsContainer 中有两个或者更多字符串有最长公共后缀，那么答案为长度 最短 的。如果有超过两个字符串有 相同 最短长度，那么答案为它们在 wordsContainer 中出现 更早 的一个。

请你返回一个整数数组 ans ，其中 ans[i]是 wordsContainer中与 wordsQuery[i] 有 最长公共后缀 字符串的下标。

示例 1：

输入：wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]
输出：[1,1,1]
解释：
我们分别来看每一个 wordsQuery[i] ：
对于 wordsQuery[0] = "cd" ，wordsContainer 中有最长公共后缀 "cd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[1] = "bcd" ，wordsContainer 中有最长公共后缀 "bcd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[2] = "xyz" ，wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 "" ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中， 答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。

示例 2：

输入：wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]
输出：[2,0,2]
解释：
我们分别来看每一个 wordsQuery[i] ：
对于 wordsQuery[0] = "gh" ，wordsContainer 中有最长公共后缀 "gh" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。
对于 wordsQuery[1] = "acbfgh" ，只有下标为 0 的字符串有最长公共后缀 "fgh" 。所以尽管下标为 2 的字符串是最短的字符串，但答案是 0 。
对于 wordsQuery[2] = "acbfegh" ，wordsContainer 中有最长公共后缀 "gh" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。

说明：

  • 1 <= wordsContainer.length, wordsQuery.length <= 10^4
  • 1 <= wordsContainer[i].length <= 5 * 10^3
  • 1 <= wordsQuery[i].length <= 5 * 10^3
  • wordsContainer[i] 只包含小写英文字母。
  • wordsQuery[i] 只包含小写英文字母。
  • wordsContainer[i].length 的和至多为 5 * 10^5 。
  • wordsQuery[i].length 的和至多为 5 * 10^5 。

思路

// todo

代码

性能

1340.跳跃游戏V

目标

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：

  • i + x ，其中 i + x < arr.length 且 0 < x <= d 。
  • i - x ，其中 i - x >= 0 且 0 < x <= d 。

除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。

你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。

请注意，任何时刻你都不能跳到数组的外面。

示例 1：

输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。

示例 2：

输入：arr = [3,3,3,3,3], d = 3
输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。

示例 3：

输入：arr = [7,6,5,4,3,2,1], d = 1
输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。

示例 4：

输入：arr = [7,1,7,1,7,1], d = 2
输出：2

示例 5：

输入：arr = [66], d = 1
输出：1

说明：

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 10^5
  • 1 <= d <= arr.length

思路

// todo

代码

性能

1345.跳跃游戏IV

目标

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

  • i + 1 需满足：i + 1 < arr.length
  • i - 1 需满足：i - 1 >= 0
  • j 需满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

示例 1：

输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。

示例 2：

输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。

示例 3：

输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。

说明：

  • 1 <= arr.length <= 5 * 10^4
  • -10^8 <= arr[i] <= 10^8

思路

有一个数组 nums，从下标 0 开始移动，目标是到达下标 n - 1。每次移动可以移动到相邻的位置，或者满足 nums[j] == nums[i] 的位置 j。返回最少移动次数。

与 3629.通过质数传送到达终点的最少跳跃次数 类似，那个题目质数列表的处理比这个相同元素列表稍微复杂一些。

思路都是 BFS，从起点出发将下一个可以到达的节点加入队列，直到到达终点。关键点是处理完一次相同元素下标列表之后要清空，避免重复访问。

小优化：只取相同元素的首尾下标。

代码


/**
 * @date 2026-05-18 8:59
 */
public class MinJumps1345 {

    public int minJumps_v1(int[] arr) {
        int n = arr.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        int i = 0;
        while (i < n) {
            int start = i;
            while (i < n && arr[i] == arr[start]) {
                i++;
            }
            map.computeIfAbsent(arr[start], x -> new ArrayList<>()).add(start);
            if (start != i - 1) {
                map.get(arr[start]).add(i - 1);
            }
        }
        List<Integer> q = new ArrayList<>();
        q.add(0);
        boolean[] visited = new boolean[n];
        int res = 0;
        while (!q.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for (Integer cur : q) {
                if (cur == n - 1) {
                    return res;
                }
                if (cur > 0 && !visited[cur - 1]) {
                    visited[cur - 1] = true;
                    tmp.add(cur - 1);
                }
                if (!visited[cur + 1]){
                    visited[cur + 1] = true;
                    tmp.add(cur + 1);
                }
                if (map.get(arr[cur]) != null) {
                    for (Integer index : map.get(arr[cur])) {
                        if (!visited[index]){
                            visited[index] = true;
                            tmp.add(index);
                        }
                    }
                    map.remove(arr[cur]);
                }
            }
            q = tmp;
            res++;
        }
        return res;
    }

}

性能

154.寻找旋转排序数组中的最小值II

目标

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
  • 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须尽可能减少整个过程的操作步骤。

示例 1：

输入：nums = [1,3,5]
输出：1

示例 2：

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

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

进阶：这道题与 153.寻找旋转排序数组中的最小值 类似，但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

思路

数组 nums 由一个升序数组经过旋转而成，求数组的最小值，要求时间复杂度为 O(log n)。

与 153.寻找旋转排序数组中的最小值 不同的是可能存在重复元素。预处理 r，使它指向不等于 nums[0] 的最大下标即可。

代码


/**
 * @date 2026-05-18 11:13
 */
public class FindMin154 {

    public int findMin(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (r >= 0 && nums[0] == nums[r]) {
            r--;
        }
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (nums[m] >= nums[0]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return nums[l % n];
    }

}

性能

1665.完成所有任务的最少初始能量

目标

给你一个任务数组 tasks ，其中 tasks[i] = [actuali, minimumi] ：

  • actuali 是完成第 i 个任务 需要耗费 的实际能量。
  • minimumi 是开始第 i 个任务前需要达到的最低能量。

比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。

你可以按照 任意顺序 完成任务。

请你返回完成所有任务的 最少 初始能量。

示例 1：

输入：tasks = [[1,2],[2,4],[4,8]]
输出：8
解释：
一开始有 8 能量，我们按照如下顺序完成任务：
    - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
    - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
    - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。

示例 2：

输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
输出：32
解释：
一开始有 32 能量，我们按照如下顺序完成任务：
    - 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
    - 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
    - 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
    - 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
    - 完成第 5 个任务，剩余能量为 9 - 8 = 1 。

示例 3：

输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
输出：27
解释：
一开始有 27 能量，我们按照如下顺序完成任务：
    - 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
    - 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
    - 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
    - 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
    - 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
    - 完成第 6 个任务，剩余能量为 12 - 6 = 6 。

说明：

  • 1 <= tasks.length <= 10^5
  • 1 <= actuali <= minimumi <= 10^4

思路

有一个二维数组 tasks，tasks[i] = [actuali, minimumi]，actuali 表示完成任务需要消耗的能量，minimumi 表示开始任务所需的最小能量。可以按任意顺序完成任务，求完成所有任务所需的最小初始能量。

//todo

代码

性能

3225.网格图操作后的最大分数

目标

给你一个大小为 n x n 的二维矩阵 grid ，一开始所有格子都是白色的。一次操作中，你可以选择任意下标为 (i, j) 的格子，并将第 j 列中从最上面到第 i 行所有格子改成黑色。

如果格子 (i, j) 为白色，且左边或者右边的格子至少一个格子为黑色，那么我们将 grid[i][j] 加到最后网格图的总分中去。

请你返回执行任意次操作以后，最终网格图的 最大 总分数。

示例 1：

输入：grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]
输出：11
解释：
第一次操作中，我们将第 1 列中，最上面的格子到第 3 行的格子染成黑色。第二次操作中，我们将第 4 列中，最上面的格子到最后一行的格子染成黑色。最后网格图总分为 grid[3][0] + grid[1][2] + grid[3][3] 等于 11 。

示例 2：

输入：grid = [[10,9,0,0,15],[7,1,0,8,0],[5,20,0,11,0],[0,0,0,1,2],[8,12,1,10,3]]
输出：94
解释：
我们对第 1 ，2 ，3 列分别从上往下染黑色到第 1 ，4， 0 行。最后网格图总分为 grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4] 等于 94 。

说明：

  • 1 <= n == grid.length <= 100
  • n == grid[i].length
  • 0 <= grid[i][j] <= 10^9

思路

代码

性能

3464.正方形上的点之间的最大距离

目标

给你一个整数 side，表示一个正方形的边长，正方形的四个角分别位于笛卡尔平面的 (0, 0) ，(0, side) ，(side, 0) 和 (side, side) 处。

同时给你一个 正整数 k 和一个二维整数数组 points，其中 points[i] = [xi, yi] 表示一个点在正方形边界上的坐标。

你需要从 points 中选择 k 个元素，使得任意两个点之间的 最小 曼哈顿距离 最大化 。

返回选定的 k 个点之间的 最小 曼哈顿距离的 最大 可能值。

两个点 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。

示例 1：

输入： side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4
输出： 2
解释：
选择所有四个点。

示例 2：

输入： side = 2, points = [[0,0],[1,2],[2,0],[2,2],[2,1]], k = 4
输出： 1
解释：
选择点 (0, 0) ，(2, 0) ，(2, 2) 和 (2, 1)。

示例 3：

输入： side = 2, points = [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k = 5
输出： 1
解释：
选择点 (0, 0) ，(0, 1) ，(0, 2) ，(1, 2) 和 (2, 2)。

说明：

  • 1 <= side <= 10^9
  • 4 <= points.length <= min(4 side, 15 10^3)
  • points[i] == [xi, yi]
  • 输入产生方式如下：
    • points[i] 位于正方形的边界上。
    • 所有 points[i] 都 互不相同 。
  • 4 <= k <= min(25, points.length)

思路

代码

性能

2463.最小移动总距离

目标

X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [positionj, limitj] ，表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人。

每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。

所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。

任何时刻，你都可以设置 部分 机器人的移动方向。你的目标是最小化所有机器人总的移动距离。

请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。

注意：

  • 所有机器人移动速度相同。
  • 如果两个机器人移动方向相同，它们永远不会碰撞。
  • 如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
  • 如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
  • 机器人从位置 x 到位置 y 的移动距离为 |y - x| 。

示例 1：

输入：robot = [0,4,6], factory = [[2,2],[6,2]]
输出：4
解释：如上图所示：
- 第一个机器人从位置 0 沿着正方向移动，在第一个工厂处维修。
- 第二个机器人从位置 4 沿着负方向移动，在第一个工厂处维修。
- 第三个机器人在位置 6 被第二个工厂维修，它不需要移动。
第一个工厂的维修上限是 2 ，它维修了 2 个机器人。
第二个工厂的维修上限是 2 ，它维修了 1 个机器人。
总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。

示例 2：

输入：robot = [1,-1], factory = [[-2,1],[2,1]]
输出：2
解释：如上图所示：
- 第一个机器人从位置 1 沿着正方向移动，在第二个工厂处维修。
- 第二个机器人在位置 -1 沿着负方向移动，在第一个工厂处维修。
第一个工厂的维修上限是 1 ，它维修了 1 个机器人。
第二个工厂的维修上限是 1 ，它维修了 1 个机器人。
总移动距离是 |2 - 1| + |(-2) - (-1)| = 2 。没有办法得到比 2 更少的总移动距离。

说明：

  • 1 <= robot.length, factory.length <= 100
  • factory[j].length == 2
  • -10^9 <= robot[i], positionj <= 10^9
  • 0 <= limitj <= robot.length
  • 测试数据保证所有机器人都可以被维修。

思路

// todo

代码

性能

1320.二指输入的的最小距离

目标

二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。

  • 例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。

给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。

坐标 (x1,y1) 和 (x2,y2) 之间的 距离 是 |x1 - x2| + |y1 - y2|。

注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。

示例 1：

输入：word = "CAKE"
输出：3
解释： 
使用两根手指输入 "CAKE" 的最佳方案之一是： 
手指 1 在字母 'C' 上 -> 移动距离 = 0 
手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'C' 到字母 'A' 的距离 = 2 
手指 2 在字母 'K' 上 -> 移动距离 = 0 
手指 2 在字母 'E' 上 -> 移动距离 = 从字母 'K' 到字母 'E' 的距离  = 1 
总距离 = 3

示例 2：

输入：word = "HAPPY"
输出：6
解释： 
使用两根手指输入 "HAPPY" 的最佳方案之一是：
手指 1 在字母 'H' 上 -> 移动距离 = 0
手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'H' 到字母 'A' 的距离 = 2
手指 2 在字母 'P' 上 -> 移动距离 = 0
手指 2 在字母 'P' 上 -> 移动距离 = 从字母 'P' 到字母 'P' 的距离 = 0
手指 1 在字母 'Y' 上 -> 移动距离 = 从字母 'A' 到字母 'Y' 的距离 = 4
总距离 = 6

说明：

  • 2 <= word.length <= 300
  • 每个 word[i] 都是一个大写英文字母。

提示：

  • dp[i][j][k]: smallest movements when you have one finger on i-th char and the other one on j-th char already having written k first characters from word.

思路

使用两个手指录入 word 字符串，求移动距离的最小值。坐标 (x1, y1) 和 (x2, y2) 之间的 距离 是 |x1 - x2| + |y1 - y2|。字母的坐标见第一张图，起始位置的代价是 0。

定义 dp[i][c] 表示已录入 word[0 ~ i] 且另一个手指在字母 c 的最小移动距离。

假设当前字母编号 cur = word[i] - 'A', 前一个位置的字母编号 prev = word[i - 1] - 'A'，有 dp[i][c] = Math.min(dp[i - 1][c] + dis[prev][cur], dp[i - 1][cur] + dis[prev][c])。

已录入 word[0 ~ i] 两个手指的所在的字母一个是 cur，一个是 c，可以从两个状态转移过来：

  • 一手指在字母 c 不动，一根手指从 prev 移动到 cur
  • 一手指在字母 cur 不动，一根手指从 prev 移动到 c

代码


/**
 * @date 2026-04-13 10:24
 */
public class MinimumDistance1320 {

    public int minimumDistance(String word) {
        int n = word.length();
        int[][] dp = new int[n][26];
        for (int i = 1; i < n; i++) {
            int prev = word.charAt(i - 1) - 'A';
            int cur = word.charAt(i) - 'A';
            for (int c = 0; c < 26; c++) {
                dp[i][c] = Math.min(dp[i - 1][c] + dis[prev][cur], dp[i - 1][cur] + dis[prev][c]);
            }
        }
        int res = Integer.MAX_VALUE;
        for (int d : dp[n - 1]) {
            res = Math.min(res, d);
        }
        return res;
    }

}

性能

3655.区间乘法查询后的异或II

目标

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

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

  • 设定 idx = li。
  • 当 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

思路

有一个长度为 n 的数组，对该数组执行 n 次查询，每次查询从 li 开始，对相距 ki 个位置上的元素执行 nums[idx] = (nums[idx] * vi) % (10^9 + 7) 直到下标 idx > ri。求处理完所有查询后 nums 中所有元素的 按位异或 结果。

可以参考差分数组的思想，采用商分数组。为每一个 ki 创建一个商分数组，需要更新的下标为 l、l + ki、l + 2 * ki、……、l + x * ki。如何确定最后一个下标？使用 r - l 将区间平移至 [0, r - l]，距离右端点最近的距离为 (r - l) % k，因此原区间 [l, r] 的最后一个下标是 r - (r - l) % k。对于商分数组，需要在 l 处乘以 vi，在 r - (r - l) % k + k 处除以 vi。由于涉及到取模，这里需要求 vi 的逆元，根据 费马小定理 等价于计算 vi^(p - 2) % p，可以使用快速幂。

暴力解法的时间复杂度为 O(q * n / k)，其中 q 为查询数组长度，n 为 nums 长度，k 为所有查询中 ki 的均值，商分数组的时间复杂度为 O(q * logM + k * n)，logM 为快速幂求逆元的时间复杂度，M = 10^9 + 7，k * n 的复杂度用于遍历每一个 ki 的商分数组，内部是根据起点分组的 0 ~ ki - 1，步长为 ki。

可以发现暴力解法的复杂度 k 越大越好，而商分数组的解法 k 越小越好。可以设置一个阈值 S，小于 S 使用商分数组，大于等于 S 使用暴力解法，时间复杂度为 O(q * n / S + S * n)。根据基本不等式 a + b >= 2sqrt(ab)，当 a == b 时取等号，因此 q/S + S >= 2 * sqrt(q)，当 S = sqrt(q) 时取得最小值。

代码

性能