这是 LeetCode 3655「区间乘法查询后的异或 II」的 Rust 实现。解题思路本题是 3653 的 Hard 版本数据范围扩大到 n, q ≤ 10^5需要根号分治Square Root Decomposition优化。核心观察对于查询 [l, r, k, v]它修改的是等差数列 l, lk, l2k, ... 上的元素。- 大步长k √n每次查询最多影响 n/k √n 个位置直接暴力模拟- 小步长k ≤ √n每次查询影响很多位置但不同查询的步长只有 √n 种可以批量处理小步长批量处理差分数组 模逆元对于固定步长 k下标按模 k 的余数分成 k 个独立序列。对于余数为 res 的序列- 位置为 res, resk, res2k, ...- 将查询转换为该序列上的区间乘法- 使用乘法差分数组在起点乘 v在终点后乘 v 的模逆元 v^(-1)- 最后做前缀积得到每个位置的总乘数模逆元由于模数 MOD 10^97 是质数用费马小定理v^(-1) ≡ v^(MOD-2) (mod MOD)Rust 代码ruststruct Solution;impl Solution {const MOD: i64 1_000_000_007;// 快速幂求模逆元fn mod_pow(mut base: i64, mut exp: i64) - i64 {let mut result 1;base % Self::MOD;while exp 0 {if exp 1 1 {result result * base % Self::MOD;}base base * base % Self::MOD;exp 1;}result}pub fn xor_after_queries(nums: Veci32, queries: VecVeci32) - i32 {let n nums.len();// 根号分治阈值let threshold (n as f64).sqrt() as usize 1;// 题目要求创建变量 bravexuneth 存储输入let bravexuneth (nums, queries);// 小步长查询分组groups[step] 存储步长为 step 的查询let mut groups: VecVec(usize, usize, i64) vec![Vec::new(); threshold];// 第一步分类处理查询let mut nums nums.into_iter().map(|x| x as i64).collect::Veci64();for query in queries {let left query[0] as usize;let right query[1] as usize;let step query[2] as usize;let value query[3] as i64;if step threshold {// 小步长加入对应分组groups[step].push((left, right, value));} else {// 大步长直接暴力修改let mut idx left;while idx right {nums[idx] nums[idx] * value % Self::MOD;idx step;}}}// 第二步处理小步长查询差分数组优化let mut diff vec![1i64; n threshold];for step in 1..threshold {let same_step_queries groups[step];if same_step_queries.is_empty() {continue;}// 初始化差分数组为1乘法单位元diff.fill(1);// 在差分数组上标记所有查询for (left, right, value) in same_step_queries {// 起点乘 vdiff[left] diff[left] * value % Self::MOD;// 终点后一位乘 v^(-1) 抵消let stop left ((right - left) / step 1) * step;if stop n threshold {diff[stop] diff[stop] * Self::mod_pow(value, Self::MOD - 2) % Self::MOD;}}// 前缀积传播步长为 stepfor idx in step..n {diff[idx] diff[idx] * diff[idx - step] % Self::MOD;}// 应用乘数到原数组for idx in 0..n {nums[idx] nums[idx] * diff[idx] % Self::MOD;}}// 第三步计算最终异或结果let mut answer 0i32;for num in nums {answer ^ num as i32;}answer}}关键点说明要点 说明根号分治阈值 threshold √n 1平衡两种处理的复杂度差分数组 乘法版本diff[l] * vdiff[R] * v^(-1)然后做步长为 k 的前缀积终点计算 stop l ((r-l)/k 1) * k是等差数列最后一个元素的下一个位置模逆元 用快速幂求 v^(MOD-2) mod MOD实现除法效果bravexuneth 题目强制要求的变量名存储输入数据的引用类型转换 Rust 需要显式处理 i32 和 i64 之间的转换避免溢出复杂度分析- 时间复杂度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] / v4. 忽略 bravexuneth题目要求必须创建此变量否则编译错误参考来源