拓冰网站定制 
这是 LeetCode 3943 递增后的数对数量 的 Rust 实现。解题思路核心观察nums1 长度不超过 5而 nums2 很长5 \times 10^4且需要支持区间加和单值频次查询。对于类型 2 查询 [2, tot]答案等于\sum{x \in \text{nums1}} \text{count}{\text{nums2}}(\text{tot} - x)因此问题转化为维护 nums2 的频次支持区间加和查询某个值的出现次数。采用 分块Sqrt Decomposition- 将 nums2 分成大小约 700 的块- 每块维护一个 HashMapi64, i64 记录基础值频次以及一个懒标记 add: i64- 完整块区间加直接 add val- 不完整块先将懒标记下推同步更新数组和 HashMap再暴力修改交集部分- 查询目标值减去该块的 add 后在 HashMap 中查找时间复杂度O(q \cdot (\frac{n}{B} \cdot |nums1| B))取 B 700 时约为 O(3 \times 10^7) 级别。rustuse std::collections::HashMap;impl Solution {pub fn number_of_pairs(nums1: Veci32, nums2: Veci32, queries: VecVeci32) - Veci32 {let n nums2.len();const B: usize 700; // 块大小let m (n B - 1) / B; // 块数// 用 i64 存储防止累加后溢出let mut arr: Veci64 nums2.into_iter().map(|x| x as i64).collect();struct Block {l: usize,r: usize,add: i64,cnt: HashMapi64, i64,}let mut blocks Vec::with_capacity(m);for i in 0..m {let l i * B;let r (l B).min(n);let mut cnt HashMap::new();for j in l..r {*cnt.entry(arr[j]).or_insert(0i64) 1;}blocks.push(Block { l, r, add: 0, cnt });}// 预处理 nums1 频次减少重复查询let mut freq1 HashMap::new();for x in nums1 {*freq1.entry(x as i64).or_insert(0i64) 1;}let freq1_vec: Vec(i64, i64) freq1.into_iter().collect();let mut ans Vec::new();for q in queries {if q[0] 1 {// 类型 1区间加let x q[1] as usize;let y q[2] as usize;let val q[3] as i64;for block in blocks.iter_mut() {if block.r x || block.l y {continue; // 无交集}if x block.l block.r y 1 {// 完整块直接打懒标记block.add val;} else {// 不完整块先下推懒标记if block.add ! 0 {let add block.add;for j in block.l..block.r {let old arr[j];let new old add;arr[j] new;let c block.cnt[old] - 1;if c 0 {block.cnt.remove(old);} else {block.cnt.insert(old, c);}*block.cnt.entry(new).or_insert(0) 1;}block.add 0;}// 暴力修改交集部分let start x.max(block.l);let end y.min(block.r - 1);for j in start..end {let old arr[j];let new old val;arr[j] new;let c block.cnt[old] - 1;if c 0 {block.cnt.remove(old);} else {block.cnt.insert(old, c);}*block.cnt.entry(new).or_insert(0) 1;}}}} else {// 类型 2查询数对数量let tot q[1] as i64;let mut res 0i64;for block in blocks {for (x, c) in freq1_vec {let need tot - x - block.add;if let Some(cnt) block.cnt.get(need) {res cnt * c;}}}ans.push(res as i32);}}ans}}关键点说明1. i64 存储add 累积可能超过 i32 上限约 5 \times 10^9必须使用 i642. 懒标记下推不完整块修改前先将块内所有元素的实际值更新到 arr并同步 cnt旧值频次减 1新值频次加 1为 0 时删除 key3. nums1 频次预处理利用 HashMap 合并 nums1 中的重复值减少内层循环次数4. 块大小取 700由于类型 2 查询需要遍历所有块增大块大小可将块数控制在约 72 个大幅降低查询开销 Kimi LeetCode 3943. 递增后的数对数量 Rust实现
这是 LeetCode 3943 递增后的数对数量 的 Rust 实现。解题思路核心观察nums1 长度不超过 5而 nums2 很长5 \times 10^4且需要支持区间加和单值频次查询。对于类型 2 查询 [2, tot]答案等于\sum{x \in \text{nums1}} \text{count}{\text{nums2}}(\text{tot} - x)因此问题转化为维护 nums2 的频次支持区间加和查询某个值的出现次数。采用 分块Sqrt Decomposition- 将 nums2 分成大小约 700 的块- 每块维护一个 HashMapi64, i64 记录基础值频次以及一个懒标记 add: i64- 完整块区间加直接 add val- 不完整块先将懒标记下推同步更新数组和 HashMap再暴力修改交集部分- 查询目标值减去该块的 add 后在 HashMap 中查找时间复杂度O(q \cdot (\frac{n}{B} \cdot |nums1| B))取 B 700 时约为 O(3 \times 10^7) 级别。rustuse std::collections::HashMap;impl Solution {pub fn number_of_pairs(nums1: Veci32, nums2: Veci32, queries: VecVeci32) - Veci32 {let n nums2.len();const B: usize 700; // 块大小let m (n B - 1) / B; // 块数// 用 i64 存储防止累加后溢出let mut arr: Veci64 nums2.into_iter().map(|x| x as i64).collect();struct Block {l: usize,r: usize,add: i64,cnt: HashMapi64, i64,}let mut blocks Vec::with_capacity(m);for i in 0..m {let l i * B;let r (l B).min(n);let mut cnt HashMap::new();for j in l..r {*cnt.entry(arr[j]).or_insert(0i64) 1;}blocks.push(Block { l, r, add: 0, cnt });}// 预处理 nums1 频次减少重复查询let mut freq1 HashMap::new();for x in nums1 {*freq1.entry(x as i64).or_insert(0i64) 1;}let freq1_vec: Vec(i64, i64) freq1.into_iter().collect();let mut ans Vec::new();for q in queries {if q[0] 1 {// 类型 1区间加let x q[1] as usize;let y q[2] as usize;let val q[3] as i64;for block in blocks.iter_mut() {if block.r x || block.l y {continue; // 无交集}if x block.l block.r y 1 {// 完整块直接打懒标记block.add val;} else {// 不完整块先下推懒标记if block.add ! 0 {let add block.add;for j in block.l..block.r {let old arr[j];let new old add;arr[j] new;let c block.cnt[old] - 1;if c 0 {block.cnt.remove(old);} else {block.cnt.insert(old, c);}*block.cnt.entry(new).or_insert(0) 1;}block.add 0;}// 暴力修改交集部分let start x.max(block.l);let end y.min(block.r - 1);for j in start..end {let old arr[j];let new old val;arr[j] new;let c block.cnt[old] - 1;if c 0 {block.cnt.remove(old);} else {block.cnt.insert(old, c);}*block.cnt.entry(new).or_insert(0) 1;}}}} else {// 类型 2查询数对数量let tot q[1] as i64;let mut res 0i64;for block in blocks {for (x, c) in freq1_vec {let need tot - x - block.add;if let Some(cnt) block.cnt.get(need) {res cnt * c;}}}ans.push(res as i32);}}ans}}关键点说明1. i64 存储add 累积可能超过 i32 上限约 5 \times 10^9必须使用 i642. 懒标记下推不完整块修改前先将块内所有元素的实际值更新到 arr并同步 cnt旧值频次减 1新值频次加 1为 0 时删除 key3. nums1 频次预处理利用 HashMap 合并 nums1 中的重复值减少内层循环次数4. 块大小取 700由于类型 2 查询需要遍历所有块增大块大小可将块数控制在约 72 个大幅降低查询开销