这是 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`，在 `t2+1` 处乘 `v` 的模逆元。
3. 模逆元：`v⁻¹ ≡ v^(MOD-2) (mod MOD)`，通过 `pow(v, MOD-2, MOD)` 计算。
Python3 实现
```python
import math
from typing import List
class Solution:
def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
MOD = 1_000_000_007
n = 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 % MOD
else:
# 小步长：用差分思想，按 (l % k) 分组
res = l % k
t1 = (l - res) // k # 在链上的起始位置
t2 = (r - res) // k # 在链上的结束位置
events[k][res].append((t1, v))
# 在 t2+1 处放置逆元，实现差分（类似前缀和的结束标记）
max_t = (n - 1 - res) // k
if 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 = 1
ptr = 0
t = 0
idx = res
while idx < n:
# 应用当前位置的所有差分事件
while ptr < len(comp) and comp[ptr][0] == t:
cur = cur * comp[ptr][1] % MOD
ptr += 1
nums[idx] = nums[idx] * cur % MOD
idx += k
t += 1
# 第三步：计算最终异或结果
xr = 0
for x in nums:
xr ^= x
return 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`：题目要求必须在函数中创建该变量存储输入，否则无法通过编译。
