Kimi LeetCode 3943. 递增后的数对数量 Python3实现

这是 LeetCode 3943 递增后的数对数量 的 Python3 实现。解题思路核心观察nums1.length 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 的块减少类型 2 查询的块遍历次数- 每块维护一个 Counter 记录基础值频次以及一个懒标记 add- 完整块区间加直接 add val- 不完整块先将懒标记下推更新数组和 Counter再暴力修改- 查询目标值减去该块的 add 后在 Counter 中查找时间复杂度O(q \cdot (\frac{n}{B} \cdot |nums1| B))取 B \approx 700 时约为 O(3 \times 10^7) 级别。pythonfrom typing import Listfrom collections import defaultdict, Counterclass Solution:def numberOfPairs(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) - List[int]:n len(nums2)B 700 # 块大小调大以减少类型2查询的块遍历次数m (n B - 1) // B # 块数arr nums2[:] # 基础值不含块懒标记# 块边界 [L[i], R[i])L [i * B for i in range(m)]R [min(n, (i 1) * B) for i in range(m)]add [0] * m # 懒标记cnt [defaultdict(int) for _ in range(m)]for i in range(m):c cnt[i]for j in range(L[i], R[i]):c[arr[j]] 1# 预处理 nums1 的频次减少重复查询cnt1 Counter(nums1)items1 list(cnt1.items()) # [(值, 出现次数), ...]ans []for q in queries:if q[0] 1:x, y, val q[1], q[2], q[3]for i in range(m):l, r L[i], R[i]if r x or l y: # 无交集continueif x l and r y 1: # 完整块add[i] valelse: # 不完整块# 下推懒标记if add[i]:a add[i]c cnt[i]for j in range(l, r):old arr[j]new old aarr[j] newc[old] - 1if c[old] 0:del c[old]c[new] c.get(new, 0) 1add[i] 0# 暴力修改交集部分start max(x, l)end min(y, r - 1)c cnt[i]for j in range(start, end 1):old arr[j]new old valarr[j] newc[old] - 1if c[old] 0:del c[old]c[new] c.get(new, 0) 1else:tot q[1]res 0for i in range(m):a add[i]c cnt[i]for x, cc in items1:need tot - x - ares c.get(need, 0) * ccans.append(res)return ans关键点说明1. 块大小取 700由于类型 2 查询需要遍历所有块增大块大小可将块数控制在约 72 个大幅降低查询开销2. Counter 维护频次下推懒标记时同步更新 arr 和 cnt保证查询时只需查 tot - x - add3. nums1 频次预处理利用 Counter 合并 nums1 中的重复值减少内层循环次数4. 懒标记下推不完整块修改前先将块内所有元素的实际值更新到位避免累积误差