3655. 区间乘法查询后的异或 ii
LeetCode 每日一题复盘：3655. 区间乘法查询后的异或 II
标签： 数组 数学 根号分治 差分数组 快速幂 难度： 困难 耗时： 约 3 小时
题目描述
给你一个长度为 n 的整数数组 nums 和一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri, ki, vi]。 对于每个查询，需要按以下步骤依次执行操作：
- 设定 idx = li。
- 当 idx <= ri 时：更新 nums[idx] = (nums[idx] * vi) % (1000000007)。将 idx += ki。
在处理完所有查询后，返回数组 nums 中所有元素的按位异或结果。 (提示：数据范围极大，n 和 q 均可达 10^5)
阶段一：直觉暴力解法 (TLE)
最开始顺着题目逻辑写的模拟。测试用例全过，但在提交时遇到了“超出时间限制 (TLE)”。 失败原因分析： 遇到极端情况（如步长 ki = 1，且区间极长），双重循环的时间复杂度会飙升，无法通过 $10^5$ 级别的大数据测试。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int xorAfterQueries(int[] nums, int[][] queries) {
int MOD = 1000000007;
int[] bravexuneth;
for(int i = 0; i < queries.length; i++) {
bravexuneth = queries[i];
int li = bravexuneth[0], ri = bravexuneth[1], ki = bravexuneth[2], vi = bravexuneth[3];
int idx = li;
while(idx <= ri && idx < nums.length) {
long temp = (long)nums[idx] * vi;
nums[idx] = (int)(temp % MOD);
idx += ki;
}
}
// ... 扫尾异或计算 ...
}
}
阶段二：优化和破局思路
为了解决大数量级下的区间跳跃修改问题，引入了以下核心架构：
1.根号分治 (核心调度)： 以 $\sqrt{n}$ (即 B) 为界限。步长大的（大跳），直接用 while 暴力修改，因为跳不了几次；步长小的（小跳），走差分数组记账。
2.带步长的二维差分数组 (小跳记账)：开辟 diff[B+1][n] 数组，每一行代表一条特定步长的独立路线。在起点乘上 vi，在越界后的“取消点”进行消除。
3.乘法逆元与快速幂 (解决取模除法)：在取模规则下无法直接除以 vi 来取消标记，需要借助费马小定理求出 vi 的乘法逆元（即 $vi^{MOD-2}$），这里手写了 fastpow 快速幂算法将 $O(N)$ 优化到 $O(\log N)$。
阶段三：最终AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
int MOD = 1000000007;
public int xorAfterQueries(int[] nums, int[][] queries) {
int n = nums.length;
int B = (int)Math.sqrt(n);
// 构建二维差分账本，行代表步长 k，列代表原数组下标
int[][] diff = new int[B + 1][n];
for(int k = 1; k <= B; k++) {
Arrays.fill(diff[k], 1); // 乘法初始化必须为 1
}
int[] bravexuneth;
for(int i = 0; i < queries.length; i++) {
bravexuneth = queries[i];
int li = bravexuneth[0], ri = bravexuneth[1], ki = bravexuneth[2], vi = bravexuneth[3];
if(ki > B){
// 大跳：暴力模拟
int idx = li;
while(idx <= ri && idx < nums.length) {
long temp = (long)nums[idx] * vi;
nums[idx] = (int)(temp % MOD);
idx += ki;
}
} else {
// 小跳：差分记账
diff[ki][li] = (int)((long)diff[ki][li] * vi % MOD);
int steps = (ri - li) / ki;
int cancelidx = li + (steps + 1) * ki; // 跨出边界的取消点
// 终点取消：乘上逆元
if(cancelidx < n) {
long invV = fastpow(vi, MOD - 2);
diff[ki][cancelidx] = (int)((long)diff[ki][cancelidx] * invV % MOD);
}
}
}
// 结算差分数组并映射回原数组 nums
for(int k = 1; k <= B; k++) {
for(int i = 0; i < n; i++) {
if(i >= k) {
diff[k][i] = (int)((long)diff[k][i] * diff[k][i-k] % MOD);
}
if(diff[k][i] != 1) { // 性能优化：过滤无效的 1
nums[i] = (int)((long)nums[i] * diff[k][i] % MOD);
}
}
}
// 最终异或求和
int result = 0;
for(int i = 0; i < n; i++) {
result ^= nums[i];
}
return result;
}
// 快速幂工具方法
private long fastpow(long a, long b) {
long res = 1;
a = a % MOD;
while(b > 0){
if(b % 2 == 1) {
res = (res * a) % MOD;
}
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
}
踩坑与复盘心得
1.数组越界血泪史： 初始化二维差分数组时，循环条件错写成了 k <= B + 1，导致在处理短数组（B较小）时直接抛出 Index 2 out of bounds for length 2。教训： 二维数组开辟了 B+1 行，合法的最大行下标就是 B，千万不能越界。
2.大数相乘必转 long： 运算 nums[idx] * vi 前，如果不强转 long，遇到两个极大 int 相乘会直接溢出成负数或乱码，取模前必须升维。
3.百川归海的顺序： 结算映射时，内部的 i >= k 前缀积滚动计算，必须放在向 nums 映射赋值的前面，顺序绝对不能乱。