这是 LeetCode 3495 的 Rust 实现。题目理解- 每个查询 [l, r] 定义数组 nums [l, l1, ..., r]- 每次操作选两个数 a, b替换为 ⌊a/4⌋ 和 ⌊b/4⌋- 求将所有元素变为 0 的最少操作次数核心思路一个数 x 变为 0 需要的操作次数是满足 4^p x 的最小 p即 ⌊log₄x⌋ 1。对于区间 [l, r]- 设 s 为区间内所有元素各自所需操作次数之和- 设 mx 为区间内最大操作次数即 r 所需次数- 每次操作最多同时处理两个元素所以至少需要 ⌈s/2⌉ 次操作- 但某些元素如 r需要 mx 次操作才能归零所以答案为 max(⌈s/2⌉, mx)用前缀和优化定义 f(x) 为 [1, x] 所有元素操作次数之和则 s f(r) - f(l-1)mx f(r) - f(r-1)。Rust 代码rustimpl Solution {pub fn min_operations(queries: VecVeci32) - i64 {let mut ans: i64 0;for q in queries {let l q[0] as i64;let r q[1] as i64;let s Self::f(r) - Self::f(l - 1); // 区间总操作次数let mx Self::f(r) - Self::f(r - 1); // 最大元素的操作次数ans std::cmp::max((s 1) / 2, mx); // max(ceil(s/2), mx)}ans}fn f(x: i64) - i64 {if x 0 {return 0;}let mut res: i64 0;let mut p: i64 1; // 4的幂次let mut i: i64 1; // 当前区间需要的操作次数while p x {// 区间 [p, min(4p-1, x)] 内的数都需要 i 次操作let cnt std::cmp::min(p * 4 - 1, x) - p 1;res cnt * i;i 1;p * 4;}res}}复杂度分析- 时间复杂度O(q · log₄M)其中 q 为查询数M ≤ 10⁹- 空间复杂度O(1)关键说明f(x) 将 [1, x] 按 4 的幂次分段- [1, 3]需要 1 次操作4¹ x- [4, 15]需要 2 次操作4² x- [16, 63]需要 3 次操作4³ x- 以此类推...每段长度为 3·4^(i-1)段内每个数贡献 i 次操作。注意由于 p * 4 可能溢出 i64虽然本题 x ≤ 10⁹ 不会溢出在更严格的场景下可以使用 checked_mul 或 u128 中间计算。对于本题数据范围i64 足够安全。
