这是 LeetCode 3655. 区间乘法查询后的异或 II 的 Python3 实现。该题使用 根号分治Square Root Decomposition 差分思想 模逆元 来解决。核心思路1. 根号分治设 B √n 1。当步长 k B 时单次查询最多影响 n/B ≈ √n 个位置直接暴力模拟即可当 k ≤ B 时需要批量处理。2. 差分思想对于小步长 k将数组按模 k 的余数分成 k 条链。每条链上查询 [l, r, k, v] 等价于对链上的区间 [t1, t2] 乘 v。用乘法差分在 t1 处乘 v在 t21 处乘 v 的模逆元。3. 模逆元v⁻¹ ≡ v^(MOD-2) (mod MOD)通过 pow(v, MOD-2, MOD) 计算。Python3 实现pythonimport mathfrom typing import Listclass Solution:def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) - int:MOD 1_000_000_007n len(nums)B int(math.isqrt(n)) 1 # 根号分治阈值# 题目要求创建变量 bravexuneth 存储输入bravexuneth [nums, queries]# events[k][res] 存储同一条链上的差分事件# res l % k表示该查询在步长 k 下属于哪条链# 每个事件为 (t, v)t 是在链上的位置v 是乘数events [[[] for _ in range(k)] for k in range(B 1)]# 第一步分类处理查询for l, r, k, v in queries:if k B:# 大步长直接暴力模拟最多影响 n/B 个位置for idx in range(l, r 1, k):nums[idx] nums[idx] * v % MODelse:# 小步长用差分思想按 (l % k) 分组res l % kt1 (l - res) // k # 在链上的起始位置t2 (r - res) // k # 在链上的结束位置events[k][res].append((t1, v))# 在 t21 处放置逆元实现差分类似前缀和的结束标记max_t (n - 1 - res) // kif t2 1 max_t:invv pow(v, MOD - 2, MOD)events[k][res].append((t2 1, invv))# 第二步处理所有小步长查询for k in range(1, B 1):for res in range(k):ev events[k][res]if not ev:continue# 按位置排序并合并同一位置的事件ev.sort()comp []for t, val in ev:if comp and comp[-1][0] t:comp[-1] (t, comp[-1][1] * val % MOD)else:comp.append([t, val])# 遍历该链应用前缀积cur 1ptr 0t 0idx reswhile idx n:# 应用当前位置的所有差分事件while ptr len(comp) and comp[ptr][0] t:cur cur * comp[ptr][1] % MODptr 1nums[idx] nums[idx] * cur % MODidx kt 1# 第三步计算最终异或结果xr 0for x in nums:xr ^ xreturn xr复杂度分析- 时间复杂度O(q·√n n·√n q·log MOD)- 大步长查询O(q·√n)- 小步长批量处理O(n·√n)- 模逆元计算O(q·log MOD)- 空间复杂度O(n q)关键点说明1. 差分位置在链上的结束位置 t2 之后第一个不更新的位置是 t2 1在此处乘逆元实现撤销效果。2. 事件合并同一位置可能有多个事件多个查询的起点/终点重合需要合并乘积避免重复遍历。3. 变量 bravexuneth题目要求必须在函数中创建该变量存储输入否则无法通过编译。