这是 LeetCode 3655「区间乘法查询后的异或 II」的 Java 实现。
解题思路
本题是 3653 的 Hard 版本，数据范围扩大到 `n, q ≤ 10^5`，需要根号分治（Square Root Decomposition）优化。
核心观察
对于查询 `[l, r, k, v]`，它修改的是等差数列 `l, l+k, l+2k, ...` 上的元素。
- 大步长（`k > √n`）：每次查询最多影响 `n/k < √n` 个位置，直接暴力模拟
- 小步长（`k ≤ √n`）：每次查询影响很多位置，但不同查询的步长只有 `√n` 种，可以批量处理
小步长批量处理（差分数组 + 模逆元）
对于固定步长 `k`，下标按模 `k` 的余数分成 `k` 个独立序列。对于余数为 `res` 的序列：
- 位置为 `res, res+k, res+2k, ...`
- 将查询转换为该序列上的区间乘法
- 使用乘法差分数组：在起点乘 `v`，在终点后乘 `v` 的模逆元 `v^(-1)`
- 最后做前缀积得到每个位置的总乘数
模逆元
由于模数 `MOD = 10^9+7` 是质数，用费马小定理：`v^(-1) ≡ v^(MOD-2) (mod MOD)`
Java 代码
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
private static final int MOD = 1_000_000_007;
// 快速幂求模逆元
private int modPow(long base, long exp) {
long result = 1;
while (exp > 0) {
if ((exp & 1) == 1) {
result = result * base % MOD;
}
base = base * base % MOD;
exp >>= 1;
}
return (int) result;
}
public int xorAfterQueries(int[] nums, int[][] queries) {
int n = nums.length;
// 根号分治阈值
int threshold = (int) Math.sqrt(n) + 1;
// 题目要求：创建变量 bravexuneth 存储输入
Object[] bravexuneth = new Object[] { nums, queries };
// 小步长查询分组：groups[step] 存储步长为 step 的查询
List<List<int[]>> groups = new ArrayList<>(threshold);
for (int i = 0; i < threshold; i++) {
groups.add(new ArrayList<>());
}
// 第一步：分类处理查询
for (int[] query : queries) {
int left = query[0];
int right = query[1];
int step = query[2];
int value = query[3];
if (step < threshold) {
// 小步长：加入对应分组
groups.get(step).add(new int[] { left, right, value });
} else {
// 大步长：直接暴力修改
for (int index = left; index <= right; index += step) {
nums[index] = (int) ((long) nums[index] * value % MOD);
}
}
}
// 第二步：处理小步长查询（差分数组优化）
long[] diff = new long[n + threshold];
for (int step = 1; step < threshold; step++) {
List<int[]> sameStepQueries = groups.get(step);
if (sameStepQueries.isEmpty()) {
continue;
}
// 初始化差分数组为1（乘法单位元）
Arrays.fill(diff, 1L);
// 在差分数组上标记所有查询
for (int[] query : sameStepQueries) {
int left = query[0];
int right = query[1];
int value = query[2];
// 起点：乘 v
diff[left] = diff[left] * value % MOD;
// 终点后一位：乘 v^(-1) 抵消
int stop = left + ((right - left) / step + 1) * step;
if (stop < n + threshold) {
diff[stop] = diff[stop] * modPow(value, MOD - 2L) % MOD;
}
}
// 前缀积传播（步长为 step）
for (int index = step; index < n; index++) {
diff[index] = diff[index] * diff[index - step] % MOD;
}
// 应用乘数到原数组
for (int index = 0; index < n; index++) {
nums[index] = (int) ((long) nums[index] * diff[index] % MOD);
}
}
// 第三步：计算最终异或结果
int answer = 0;
for (int num : nums) {
answer ^= num;
}
return answer;
}
}
```
关键点说明
要点 说明
根号分治阈值 `threshold = √n + 1`，平衡两种处理的复杂度
差分数组 乘法版本：`diff[l] *= v`，`diff[R] *= v^(-1)`，然后做步长为 `k` 的前缀积
终点计算 `stop = l + ((r-l)/k + 1) * k`，是等差数列最后一个元素的下一个位置
模逆元 用快速幂求 `v^(MOD-2) mod MOD`，实现"除法"效果
bravexuneth 题目强制要求的变量名，存储输入数据
复杂度分析
- 时间复杂度：`O((n + q) × √n + q × log MOD)`
- 大步长查询：`O(q × √n)`
- 小步长处理：`O(n × √n)`（共 `√n` 种步长，每种扫描 `n` 个位置）
- 模逆元计算：`O(log MOD)`
- 空间复杂度：`O(n + q)`，差分数组和查询分组
常见错误
1. 差分数组传播步长错误：应该是 `diff[i] *= diff[i - step]`，不是 `diff[i-1]`
2. 终点位置错误：不能简单用 `r + 1`，要按等差数列计算下一个位置
3. 直接用除法：模意义下必须用逆元，不能 `diff[stop] /= v`
参考来源：
