欢迎大家加QQ群：623375442。
Q1. Partition Array into Two Equal Product Subsets
给你一个整数数组 nums，其中包含的正整数 互不相同 ，另给你一个整数 target。
请判断是否可以将 nums 分成两个 非空、互不相交 的 子集 ，并且每个元素必须 恰好 属于 一个 子集，使得这两个子集中元素的乘积都等于 target。
如果存在这样的划分，返回 true；否则，返回 false。
子集 是数组中元素的一个选择集合。
测试样例：
输入：nums = [3,1,6,8,4], target = 24
输出：true
解释：子集 [3, 8] 和 [1, 6, 4] 的乘积均为 24。因此，输出为 true 。
解答：
- 使用深度优先搜索（DFS），从下标 0 开始，维护三个变量：当前左子集乘积 left、当前右子集乘积 right、目标值 target。
- 递归到第 pos 个元素时，将 nums[pos] 乘到左子集或右子集中，分别记作 nextLeft 和 nextRight。如果乘积超过 target，则剪枝（因为既然都是正整数，再乘只会更大，不可能回头）。
- 当 pos 达到 nums.length 时，检查此刻 left == target && right == target，如果都满足，则说明找到了可行划分，返回 true；否则返回 false。
- 初始调用时，将 left 与 right 均设置为 -1，表示尚未放入第一个元素。对于第一次放入时，若 left == -1，则直接让 left = nums[pos] 而不做乘法，否则做正常乘法。
该方法枚举了所有把每个元素放左边或右边的可能性，总共 $2^n$ 种情况，但由于题目规模限制（数组长度一般较小）且乘积会快速剪枝，实际上可行。
class Solution {
/**
* 判断是否可以将 nums 划分为两个子集，使得两边的乘积都等于 target
* @param nums 不含重复正整数的数组
* @param target 目标乘积
* @return 如果存在可行划分返回 true，否则 false
*/
public boolean checkEqualPartitions(int[] nums, long target) {
// 从位置 0 开始，左右子集乘积都初始化为 -1，表示还未放任何元素
return dfs(nums, 0, -1, -1, target);
}
/**
* 深度优先搜索子集拆分
* @param nums 输入数组
* @param pos 当前考察的元素下标
* @param left 左子集当前乘积，-1 表示尚无元素
* @param right 右子集当前乘积，-1 表示尚无元素
* @param target 目标乘积
* @return 如果从 pos 开始能找到可行划分返回 true，否则 false
*/
private boolean dfs(int[] nums, int pos, long left, long right, long target) {
// 到达数组末尾，判断当前左右乘积是否都等于 target
if (pos == nums.length) {
return left == target && right == target;
} else {
// 尝试将 nums[pos] 放入左子集中
// 如果 left == -1（左子集还没元素），则直接赋值；否则累乘
long nextLeft = (left == -1) ? nums[pos] : (nums[pos] * left);
// 只有当 nextLeft 不超过 target 时才继续递归
if (nextLeft <= target && dfs(nums, pos + 1, nextLeft, right, target)) {
return true;
}
// 否则尝试将 nums[pos] 放入右子集中
long nextRight = (right == -1) ? nums[pos] : (nums[pos] * right);
// 只有当 nextRight 不超过 target 时才继续递归
return nextRight <= target && dfs(nums, pos + 1, left, nextRight, target);
}
}
}Q2. Minimum Absolute Difference in Sliding Submatrix
给你一个 m x n 的整数矩阵 grid 和一个整数 k。
对于矩阵 grid 中的每个连续的 k x k 子矩阵，计算其中任意两个 不同值 之间的 最小绝对差 。
返回一个大小为 (m - k + 1) x (n - k + 1) 的二维数组 ans，其中 ans[i][j] 表示以 grid 中坐标 (i, j) 为左上角的子矩阵的最小绝对差。
注意：如果子矩阵中的所有元素都相同，则答案为 0。
子矩阵 (x1, y1, x2, y2) 是一个由选择矩阵中所有满足 x1 <= x <= x2 且 y1 <= y <= y2 的单元格 matrix[x][y] 组成的矩阵。
测试样例：
输入：grid = [[1,8],[3,-2]], k = 2
输出：[[2]]
解释：
- 只有一个可能的 k x k 子矩阵：[[1, 8], [3, -2]]。
- 子矩阵中的不同值为 [1, 8, 3, -2]。
- 子矩阵中的最小绝对差为 |1 - 3| = 2。因此，答案为 [[2]]。
解答：题目给定一个大小为 m x n 的矩阵 grid 和一个整数 k。对于矩阵中每个连续的 k x k 子矩阵，需要计算其中任意两个不同值之间的最小绝对差。如果子矩阵内所有元素相同，则最小绝对差为 0。返回一个大小为 (m - k + 1) x (n - k + 1) 的矩阵 ans，其中 ans[i][j] 表示以 (i,j) 为左上角的 k x k 子矩阵的最小绝对差。
由于子矩阵的规模固定为 k x k，且 k 较小时可以直接枚举每个子矩阵再统计。步骤如下：
- 若 $k = 1$，那么每个子矩阵就是单个元素，所有元素都相同，答案为 0，因此直接返回全零矩阵。
- 否则，对每个左上角坐标 (i, j)，将这个 k k 区域内的所有元素提取到一个长度为 k k 的一维数组 sort 中。
- 对 sort 排序，然后遍历排序后数组，统计相邻不同元素之差的最小值 minDiff；若所有都相同（即排序后没有相邻元素不同），则 minDiff = 0。
- 将 ans[i][j] = minDiff。
- 由于矩阵大小为 $m \times n$，左上角坐标的遍历范围是 i = 0..m-k，j = 0..n-k。
class Solution {
/**
* 对每个 k×k 的滑动子矩阵，计算其中任意两个不同值之间的最小绝对差
* @param grid 输入的 m×n 矩阵
* @param k 子矩阵的边长
* @return 大小为 (m-k+1)×(n-k+1) 的结果矩阵 ans
*/
public int[][] minAbsDiff(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
// 结果矩阵尺寸为 (m-k+1)×(n-k+1)
int[][] res = new int[m - k + 1][n - k + 1];
// 如果 k == 1，那么每个子矩阵都是单个元素，最小差为 0
if (k == 1) return res;
// 遍历所有可能作为左上角的起点 (i,j)
for (int i = 0; i < res.length; ++i) {
for (int j = 0; j < res[i].length; ++j) {
// 用一维数组收集当前 k×k 区域的所有元素
int[] sort = new int[k * k];
int pos = 0;
for (int di = 0; di < k; ++di) {
for (int dj = 0; dj < k; ++dj) {
sort[pos++] = grid[i + di][j + dj];
}
}
// 对当前子矩阵所有值排序
Arrays.sort(sort);
// 初始化为一个较大值
res[i][j] = Integer.MAX_VALUE;
// 统计相邻不同元素的最小差值
for (int t = 1; t < k * k; ++t) {
if (sort[t] != sort[t - 1]) {
res[i][j] = Math.min(res[i][j], sort[t] - sort[t - 1]);
}
}
// 如果 res[i][j] 仍然是 Integer.MAX_VALUE，说明子矩阵所有元素都相同，最小差设为 0
if (res[i][j] == Integer.MAX_VALUE) res[i][j] = 0;
}
}
return res;
}
}Q3. Minimum Moves to Clean the Classroom
给你一个 m x n 的网格图 classroom，其中一个学生志愿者负责清理散布在教室里的垃圾。网格图中的每个单元格是以下字符之一：
- 'S' ：学生的起始位置
- 'L' ：必须收集的垃圾（收集后，该单元格变为空白）
- 'R' ：重置区域，可以将学生的能量恢复到最大值，无论学生当前的能量是多少（可以多次使用）
- 'X' ：学生无法通过的障碍物
- '.' ：空白空间
同时给你一个整数 energy，表示学生的最大能量容量。学生从起始位置 'S' 开始，带着 energy 的能量出发。
每次移动到相邻的单元格（上、下、左或右）会消耗 1 单位能量。如果能量为 0，学生此时只有处在 'R' 格子时可以继续移动，此区域会将能量恢复到 最大 能量值 energy。
返回收集所有垃圾所需的 最少 移动次数，如果无法完成，返回 -1。
测试样例：
输入：classroom = ["S.", "XL"], energy = 2
输出：2
解释:
- 学生从单元格 (0, 0) 开始，带着 2 单位的能量。
- 由于单元格 (1, 0) 有一个障碍物 'X'，学生无法直接向下移动。
- 收集所有垃圾的有效移动序列如下：
- 移动 1：从 (0, 0) → (0, 1)，消耗 1 单位能量，剩余 1 单位。
- 移动 2：从 (0, 1) → (1, 1)，收集垃圾 'L'。
学生通过 2 次移动收集了所有垃圾。因此，输出为 2。
解答：使用 BFS（广度优先搜索），定义每个状态为四元组 (i, j, mask, energyLeft)，并记录已经到达该状态时剩余能量最大的情况，若再次到达同一 i, j, mask 时，剩余能量不超过之前记录的，则无需继续，因为更高能量总是更优。
具体步骤：
- 扫描输入 classroom 数组，找到起始点 S 的坐标，记录所有垃圾 L 的坐标并编号（存到 trashMap[i][j] 中），trashCount 为垃圾总数。
- 用一个三维数组 bestEnergy[i][j][mask] 记录到达 (i,j) 并且已经收集 mask 这些垃圾时所剩的最大能量。初始时，bestEnergy[si][sj][0] = energy，并将 (si, sj, mask=0, energy, movesCount=0) 入队。
- 从队列中取出当前状态 (i,j,mask,e,movesCount)：
- 如果当前格子是 'R'，则将当前能量 energyLeft = energy（恢复满能量）；否则 energyLeft = e。
- 如果 energyLeft == 0，且当前不是 'R'，说明没法继续移动，直接跳过。
- 否则，尝试向四个方向移动到 (ni, nj)：
-检查边界与是否是 'X'，若不可通行则跳过。
-计算下一个垃圾收集状态 nextMask：如果 (ni, nj) 是 'L'，则将对应位标记为已收集。- 下一个剩余能量为 nextEnergy = energyLeft - 1（向下一个位置移动消耗 1）。
- 如果此前到达 (ni, nj, nextMask) 时记录的剩余能量 bestEnergy[ni][nj][nextMask] 大于等于 nextEnergy，说明当前路径不如历史最优，跳过。否则更新 bestEnergy[ni][nj][nextMask] = nextEnergy，并将状态 (ni, nj, nextMask, nextEnergy, movesCount+1) 入队。
- 如果当前 mask == fullMask（所有垃圾都已收集），直接返回 movesCount，即为最少移动次数。
- 若 BFS 结束仍未收集完所有垃圾，返回 -1。
class Solution {
// 定义四个方向移动的偏移量，(dx, dy) 分别是 (1,0)、(0,1)、(-1,0)、(0,-1)
private static final int[] moves = {1, 0, -1, 0, 1};
/**
* 求收集所有垃圾所需的最少移动次数
* @param classroom 输入的网格，每个字符表示不同含义
* @param energy 学生的最大能量
* @return 如果能收集完所有垃圾，返回最少移动次数；否则返回 -1
*/
public int minMoves(String[] classroom, int energy) {
int m = classroom.length, n = classroom[0].length();
int[] student = null; // 用于记录起始位置 S 的坐标
int[][] trashMap = new int[m][n]; // 对于每个 'L' 垃圾，存储其编号
int trashCount = 0; // 垃圾总数
// 第一次扫描：找到起始点 S，统计所有垃圾并编号
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
char c = classroom[i].charAt(j);
if (c == 'S') {
student = new int[]{i, j}; // 记录起始位置
} else if (c == 'L') {
// 将第 trashCount 个垃圾标号为 trashCount
trashMap[i][j] = trashCount++;
}
}
}
// fullMask 表示所有垃圾都已收集，对应二进制全 1（长度为 trashCount）
int fullMask = (1 << trashCount) - 1;
// bestEnergy[i][j][mask]：到达 (i,j) 并且已经收集 mask 状态下，所剩能量的最大值
int[][][] bestEnergy = new int[m][n][1 << trashCount];
// 初始化都为 -1，表示未到达过
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < (1 << trashCount); ++k) {
bestEnergy[i][j][k] = -1;
}
}
}
// 使用双端队列进行 BFS，每个状态记录为 [i, j, mask, energyLeft, movesCount]
ArrayDeque<int[]> queue = new ArrayDeque<>();
int si = student[0], sj = student[1];
// 初始状态：在起始点，尚未收集垃圾（mask=0），剩余能量为 energy，移动次数为 0
bestEnergy[si][sj][0] = energy;
queue.add(new int[]{si, sj, 0, energy, 0});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int i = cur[0], j = cur[1], mask = cur[2], e = cur[3], movesCount = cur[4];
// 如果已经收集完所有垃圾，直接返回移动次数
if (mask == fullMask) {
return movesCount;
}
// 如果当前在 'R' 格子上，则能量恢复为最大值
int energyLeft = e;
if (classroom[i].charAt(j) == 'R') {
energyLeft = energy;
}
// 如果能量已耗尽且不在 'R'，则无法继续移动，跳过
if (energyLeft == 0) {
continue;
}
// 向 4 个方向尝试移动
for (int k = 0; k < 4; ++k) {
int ni = i + moves[k];
int nj = j + moves[k + 1];
// 检查边界
if (ni < 0 || ni >= m || nj < 0 || nj >= n) {
continue;
}
char c = classroom[ni].charAt(nj);
// 如果是障碍 'X'，跳过
if (c == 'X') {
continue;
}
// 计算下一个垃圾收集状态
int nextMask = mask;
if (c == 'L') {
// 如果下一个格子是垃圾，就把对应位标记为已收集
nextMask = mask | (1 << trashMap[ni][nj]);
}
// 移动耗费 1 单位能量
int nextEnergy = energyLeft - 1;
// 如果到达 (ni,nj,nextMask) 时剩余能量不如之前曾到达该状态时的能量，跳过
if (bestEnergy[ni][nj][nextMask] >= nextEnergy) {
continue;
}
// 更新 bestEnergy，并将新状态入队
bestEnergy[ni][nj][nextMask] = nextEnergy;
queue.add(new int[]{ni, nj, nextMask, nextEnergy, movesCount + 1});
}
}
// BFS 结束仍没收集完所有垃圾，返回 -1
return -1;
}
}Q4. Maximize Count of Distinct Primes After Split
给你一个长度为 'n' 的整数数组 nums，以及一个二维整数数组 queries，其中 queries[i] = [idx, val]。
对于每个查询：
- 更新 nums[idx] = val。
- 选择一个满足 1 <= k < n 的整数 k ，将数组分为非空前缀 nums[0..k-1] 和后缀 nums[k..n-1]，使得每部分中 不同 质数的数量之和 最大 。
注意：每次查询对数组的更改将持续到后续的查询中。
返回一个数组，包含每个查询的结果，按给定的顺序排列。
质数是大于 1 的自然数，只有 1 和它本身两个因数。
测试样例：
输入：nums = [2,1,3,1,2], queries = [[1,2],[3,3]]
输出：[3.4]
解释:
- 初始时 nums = [2, 1, 3, 1, 2]。
- 在第一次查询后，nums = [2, 2, 3, 1, 2]。将 nums 分为 [2] 和 [2, 3, 1, 2]。[2] 包含 1 个不同的质数，[2, 3, 1, 2] 包含 2 个不同的质数。所以此查询的答案是 1 + 2 = 3。
- 在第二次查询后，nums = [2, 2, 3, 3, 2]。将 nums 分为 [2, 2, 3] 和 [3, 2]，其答案为 2 + 2 = 4。
- 最终输出为 [3, 4]。
解答：给定长度为 n 的整数数组 nums，以及若干次查询 queries，每次查询包含 [idx, val]，表示执行 nums[idx] = val。在每次更新之后，需要选择一个切分点 1 < k < n，将数组分为前缀 nums[0..k-1] 和后缀 nums[k..n-1]，使得前缀中出现的不同质数数量与后缀中出现的不同质数数量之和最大。返回每次查询后的最大值。
关键在于：统计数组前缀（或后缀）中不同质数数量。若将某个质数 p 出现在索引集合 {i1, i2, ..., it}，那么不论切到哪个位置，这个质数只会计入「前面」或「后面」中某一侧。如果在切分位置左边至少包含一次 p，就算作前缀里有 p；右边至少包含一次，就算作后缀里有 p。在划分时，对于该质数，它可能出现在前缀，也可能出现在后缀，或者同时出现在两边（若在切分点两侧都有出现）。但是题目只需要“不同质数的数量之和”；注意“同一个质数分别在前后缀都出现，只算作前后各 +1”。也就是说：若 p 在前缀里出现过一次以上，就贡献 +1；若 p 在后缀里出现过一次以上，也贡献 +1。如果全部出现都在前缀或都在后缀，则只贡献 +1。
我们需要在每次查询后，快速维护以下两项信息：
- 全局不同质数数目：即数组中出现的所有不同质数的总数 primeCount。如果一个质数当前在数组中位置集合空了（被覆盖掉或变成合数），全局数量减少 1；若新增出现，就全局数量加 1。
- 切分后，能够“额外”贡献的部分：所谓“额外”是指在一种切分下，一个质数可以在前缀里和后缀里同时出现，从而贡献 2。但若某质数只出现在左侧或只出现在右侧，则仅贡献 1。若一个质数在左右两部分都出现，则它的计数 2 可以分解为 “全局算作 1” + “额外”1。换言之，总贡献 = primeCount + 额外贡献。显然，“额外贡献”最大值即为：所有质数在划分线两侧都有出现的个数最多是多少。
如何计算“额外贡献”最大值？对于某个质数 p，在数组中所有它出现的位置按索引排序，记第一个出现位置为 first，最后一次出现位置为 last。只要把切分线置于 (first+1) 到 last 之间（这段区间是能保证前缀中至少有 p，后缀中至少有 p 的切分），p 就在切分后两侧同时出现，额外能贡献 1。否则，就无法同时出现在两侧，只能贡献 0 个额外。对于所有质数，把它们各自 (first+1, last) 区间视为 “质数 p 能获得额外贡献的切分范围”。要让额外贡献最大，我们需要在 $[1, n-1]$ 的切分线范围内，找到一个位置 k，使得落入最多这些区间内。即对若干个开区间（其实左闭右闭都可以，后面实现里是用 [first+1, last] 形式），找一个点使得包含该点的区间数最大。经典做法是：用线段树或差分＋扫描线，实际上需要支持动态维护这些区间长度，在每次更新时更新对应质数的 (first, last) 值并维护一个线段树来快速查询 “在 1..n-1 中哪个点被覆盖次数最多”。
实现思路：
- 先用筛法预处理出 isPrimeArr[x] 判断 x <= 100000 是否为质数。
- 用一个 Map<Integer, TreeSet
> posMap，记录每个质数 p 对应在数组中的出现位置集合（使用 TreeSet 便于取最小/最大位置）。 - 全局不同质数数 primeCount = posMap.size()。
- 同时，新建一个线段树 SegmentTree tree，它管理区间 [0..n]，在后续查询中只关心范围 [1..n-1]。线段树支持区间加值和查询区间最大值。初始化时，对于每个在数组中出现的质数 p，取其在 posMap 中的最小位置 first, 最大位置 last，然后在 tree.update(first+1, last, +1)，表示在 first+1 到 last 的每个切分点都能让 p 同时分到两边（贡献额外 1）。
- 对于每次查询 (idx,val)：
- 令 oldVal = nums[idx]。如果 oldVal 是质数：
- 先把它从 posMap.get(oldVal) 中移除坐标 idx。在移除前，需要在 tree 中执行一次 tree.update(first+1, last, -1)，取消之前基于 oldVal 的区间贡献；更新后，如果集合不为空，取新的 first、last，再执行 tree.update(newFirst+1, newLast, +1)；如果移除后集合为空，则该质数不再存在于数组中，primeCount--。
- 将 nums[idx] = val。如果 val 是质数：
- 若此前未出现过，posMap.put(val, new TreeSet<>)，然后 primeCount++，并直接把 idx 放入 TreeSet，此时只有一个位置，暂时无法构成一条区间（因为 first == last，切分范围为空），后续再有新位置时会更新。
- 若此前已出现过，需要先取原来的 first, last，在 tree.update(first+1, last, -1) 撤销之前区间。然后把 idx 加入 TreeSet，取新的 first, last，执行 tree.update(newFirst+1, newLast, +1)。
- 以上完成后，primeCount 已更新；线段树中记录了当前所有质数对应区间对切分点的覆盖数。此时查询线段树 (1, n-1) 上的最大值 maxExtra = tree.queryMax(1, n-1)，即“额外贡献”的最大可能；最终答案为 primeCount + maxExtra。
- 令 oldVal = nums[idx]。如果 oldVal 是质数：
- 将每次查询的结果存入数组返回。
class Solution {
// 预设最大值上界，方便一次性筛出所有 <= maxVal 的质数
private static final int maxVal = 100000;
// 用布尔数组标记索引对应是否为质数
private static final boolean[] isPrimeArr = new boolean[maxVal + 1];
// 静态块中执行埃拉托色尼筛法，初始化 isPrimeArr
static {
Arrays.fill(isPrimeArr, true);
isPrimeArr[0] = false;
isPrimeArr[1] = false;
for (int i = 2; i * i <= maxVal; i++) {
if (isPrimeArr[i]) {
for (int j = i * i; j <= maxVal; j += i) {
isPrimeArr[j] = false;
}
}
}
}
/**
* 对于每次查询更新 nums[idx] = val 后，求能最大化前后缀不同质数数量之和
* @param nums 初始数组
* @param queries 每个查询为 [idx, val]
* @return 每次查询后的答案数组
*/
public int[] maximumCount(int[] nums, int[][] queries) {
int n = nums.length;
// posMap：质数值 -> 该质数在 nums 中所有出现位置的有序集合
Map<Integer, TreeSet<Integer>> posMap = new HashMap<>();
// 先把初始数组中的所有质数的位置存到 posMap 中
for (int i = 0; i < n; ++i) {
int val = nums[i];
if (val <= maxVal && isPrimeArr[val]) {
// 若该质数第一次出现，需要 new 一个 TreeSet
if (!posMap.containsKey(val)) {
posMap.put(val, new TreeSet<>());
}
posMap.get(val).add(i);
}
}
// primeCount 为当前数组中不同质数的总数
int primeCount = posMap.size();
// 线段树管理的区间为 [0..n]，实际查询我们只关注 [1..n-1] 切分点
SegmentTree tree = new SegmentTree(n);
// 对于初始数组中每个质数 p，取其最小、最大下标 first, last
// 并在区间 [first+1, last] 上加 1，表示在这些切分点 p 可同时分到两边
for (Map.Entry<Integer, TreeSet<Integer>> entry : posMap.entrySet()) {
TreeSet<Integer> set = entry.getValue();
update(set, tree, 1);
}
int q = queries.length;
int[] res = new int[q];
// 遍历每次查询
for (int i = 0; i < q; i++) {
int idx = queries[i][0];
int val = queries[i][1];
int oldVal = nums[idx];
// 处理 oldVal：如果 oldVal 是质数，需要从 posMap 中移除 idx
if (oldVal <= maxVal && isPrimeArr[oldVal]) {
TreeSet<Integer> set = posMap.get(oldVal);
// 先撤销当前质数对应的贡献区间：-1
update(set, tree, -1);
set.remove(idx);
if (set.isEmpty()) {
// 如果移除后该质数彻底不在数组中，删除映射，primeCount 减 1
posMap.remove(oldVal);
--primeCount;
} else {
// 否则取更新后的 first, last，再次在新区间加 +1
update(set, tree, 1);
}
}
// 更新 nums[idx] = val
nums[idx] = val;
// 处理新值 val：如果 val 是质数，需要加入 posMap
if (val <= maxVal && isPrimeArr[val]) {
if (!posMap.containsKey(val)) {
// 第一次出现该质数，创建 TreeSet
posMap.put(val, new TreeSet<>());
}
TreeSet<Integer> set = posMap.get(val);
if (set.isEmpty()) {
// 如果之前没出现，先把 idx 加进去，然后 primeCount++
set.add(idx);
++primeCount;
// 只有一个位置时 first == last，无需在线段树上更新区间
} else {
// 如果之前已经存在，则先撤销旧区间贡献
update(set, tree, -1);
set.add(idx);
// 再应用新区间贡献
update(set, tree, 1);
}
}
// 当前 primeCount 已维护完毕，再查询线段树 [1..n-1] 的最大值
int maxExtra = 0;
if (n > 1) {
maxExtra = tree.queryMax(1, n - 1);
}
// 答案 = 当前不同质数总数 + 额外贡献
res[i] = primeCount + maxExtra;
}
return res;
}
/**
* 根据 TreeSet 中记录的该质数所有出现位置，更新线段树的区间贡献
* 如果 set 中只有一个元素 (first == last)，说明没有开区间可更新
* 否则，对 [first+1, last] 区间进行加 val（val=1 表示添加，val=-1 表示撤销）
*
* @param set 存储某质数出现的所有位置的有序集合
* @param tree 线段树
* @param val 更新量（+1 或 -1）
*/
private void update(TreeSet<Integer> set, SegmentTree tree, int val) {
// 若该质数目前没有位置（说明空集合、刚删除完），不做处理
if (set.isEmpty()) return;
int first = set.first();
int last = set.last();
// 只有当 last > first 时，才能让切分点落在它们之间
if (last > first) {
// 在 [first+1, last] 的区间内加上 val
tree.update(first + 1, last, val);
}
}
}
/**
* 支持区间加值、区间最大值查询的线段树
* 范围维护 [0..n]，但我们只会在 [1..n-1] 上执行查询
*/
class SegmentTree {
int n;
int[] max; // 记录当前节点管理区间的最大覆盖数
int[] lazy; // 懒惰标记，用于区间添加延迟更新
public SegmentTree(int size) {
n = size;
max = new int[4 * n];
lazy = new int[4 * n];
}
/**
* 在 [l..r] 区间上加上 val（val 可以为正负）
* @param l 左边界（包含）
* @param r 右边界（包含）
* @param val 更新量
*/
public void update(int l, int r, int val) {
update(1, 0, n, l, r, val);
}
// 私有递归方法，在节点 node 管理的 [nl..nr] 范围上更新 [l..r]
private void update(int node, int nl, int nr, int l, int r, int val) {
// 如果 [l..r] 与 [nl..nr] 不相交，则直接返回
if (r < nl || nr < l) {
return;
}
// 如果 [l..r] 完全覆盖 [nl..nr]，直接打懒标记
if (l <= nl && nr <= r) {
apply(node, val);
return;
}
// 否则需要先下推懒标记，再分段更新
push(node);
int mid = (nl + nr) >> 1;
update(node * 2, nl, mid, l, r, val);
update(node * 2 + 1, mid + 1, nr, l, r, val);
// 更新当前节点的最大值取左右子节点的最大
pull(node);
}
/**
* 查询区间 [l..r] 上的最大值
* @param l 左边界（包含）
* @param r 右边界（包含）
* @return 区间最大值
*/
public int queryMax(int l, int r) {
return queryMax(1, 0, n, l, r);
}
// 私有递归方法，在节点 node 管理的 [nl..nr] 范围上查询 [l..r]
private int queryMax(int node, int nl, int nr, int l, int r) {
// 如果不相交，返回 0（因为不会贡献额外区间）
if (r < nl || nr < l) {
return 0;
}
// 如果节点完全在查询范围内，直接返回该节点记录的最大值
if (l <= nl && nr <= r) {
return max[node];
}
// 部分相交的情况，需要先下推懒标记，再询问左右子节点
push(node);
int mid = (nl + nr) >> 1;
return Math.max(
queryMax(node * 2, nl, mid, l, r),
queryMax(node * 2 + 1, mid + 1, nr, l, r)
);
}
// 将 val 加到当前节点的 max 和 lazy 标记上
private void apply(int node, int val) {
max[node] += val;
lazy[node] += val;
}
// 下推懒标记到子节点
private void push(int node) {
if (lazy[node] != 0) {
apply(node * 2, lazy[node]);
apply(node * 2 + 1, lazy[node]);
lazy[node] = 0;
}
}
// 拉取左右子节点的值更新当前节点的最大值
private void pull(int node) {
max[node] = Math.max(max[node * 2], max[node * 2 + 1]);
}
}