Kimi LeetCode 3911. 移除子数组元素后第 K 小偶数 Python3实现

以下是可直接在 LeetCode 提交的 Python3 完整实现，方法名已按题目要求使用 `kthRemainingInteger`：

```python
import bisect

class Solution:
def kthRemainingInteger(self, nums: list[int], queries: list[list[int]]) -> list[int]:
"""
对每个查询 [l, r, k]：
- 从无限正偶数序列 2,4,6,8,... 中移除子数组 nums[l..r] 里的偶数
- 返回剩余序列中第 k 小的偶数

核心思路：二分套二分
- 外层二分：假设答案是第 t 个正偶数（值为 2*t）
- 内层二分：统计子数组中值 <= 2*t 的偶数个数
- 验证：t - removed_count >= k 是否成立
"""

# 预处理：提取所有偶数的下标和值（nums 严格递增，故 even_val 也严格递增）
even_idx = [] # 偶数在原数组中的下标
even_val = [] # 偶数的值
for i, x in enumerate(nums):
if x % 2 == 0:
even_idx.append(i)
even_val.append(x)

m = len(even_val) # 全局偶数个数

def count_removed(l: int, r: int, t: int) -> int:
"""统计子数组 nums[l..r] 中值 <= 2*t 的偶数个数"""
# 步骤1：找到下标落在 [l, r] 范围内的偶数位置
left = bisect.bisect_left(even_idx, l)
right = bisect.bisect_right(even_idx, r)
if left >= right:
return 0

# 步骤2：在这些偶数中，值 <= 2*t 的个数（even_val 严格递增，可直接二分）
return bisect.bisect_right(even_val, 2 * t, left, right) - left

ans = []
for l, r, k in queries:
# 二分查找第 t 个正偶数
# 下界：k（至少第 k 个偶数）
# 上界：k + 全局偶数个数 + 余量（安全上界）
lo, hi = k, k + m + 2

while lo < hi:
mid = (lo + hi) // 2
removed = count_removed(l, r, mid) # 子数组中被移除的偶数个数
remaining = mid - removed # 前 mid 个偶数中剩余的个数

if remaining >= k:
hi = mid # 答案可能更小，收缩右边界
else:
lo = mid + 1 # 剩余不够，需要更大的 t

ans.append(2 * lo) # 第 t 个正偶数的值是 2*t

return ans
```

核心思路（二分套二分）

层次 作用
外层二分 对「第 t 个正偶数」二分。若前 t 个偶数（即 2,4,\dots,2t）中，未被移除的个数 \ge k，则答案 \le 2t。
内层二分 `count_removed` 先用 `bisect_left/right` 锁定子数组区间内的偶数位置，再用 `bisect_right` 统计其中值 \le 2t 的个数。
单调性 随着 t 增大，被移除的个数只增不减，因此「剩余个数 = t - \text{removed}」单调递增，保证二分正确。

复杂度

- 时间：O((n + q) \cdot \log m \cdot \log(k+m))，其中 n = \text{len(nums)}，q = \text{len(queries)}，m 为偶数总数。
- 空间：O(n)，存储偶数下标和值。

验证结果

输入 输出
`nums=[1,4,7], queries=[[0,2,1],[1,1,2],[0,0,3]]` `[2, 6, 6]`
`nums=[2,5,8], queries=[[0,1,2],[1,2,1],[0,2,4]]` `[6, 2, 12]`
`nums=[3,6], queries=[[0,1,1],[1,1,3]]` `[2, 8]`