“区间乘法查询后的异或Ⅰ”这个标题第一眼就是典型的数据结构题。又是区间、又是乘法、又是异或看起来怎么都得线段树起步。但等我认真读完四元组[li, ri, ki, vi]的定义之后才反应过来这个题真正的考点根本不在“维护区间”而在“统计更新次数”甚至可以说是一道披着数据结构外衣的数论题。题目给定一个长度为n的整数数组nums和q条查询。每条查询给四个整数li、ri、ki、vi。按这类题最常见的设定第t条查询中的ki等同于t也就是“第几次查询”更新规则是把闭区间[li, ri]中所有满足“下标能被ki整除”的位置都乘上vi然后输出当前整个数组所有元素的异或和。如果原题把ki理解成“步长”那代码只差一行我后文也会补充。这篇文章就把这个题彻底拆开从题意还原、复杂度分析到 Go 语言实现和踩坑记录一次性说清楚适合正在刷数据结构题、想搞懂调和级数复杂度的同学参考。1. 先还原题意四元组 [li, ri, ki, vi] 到底要做什么1.1 我最初读题时的困惑第一次看到这个标题我心里其实是拒绝的。因为“区间乘法”这几个字太有迷惑性了正常人都会往线段树的懒标记方向想维护区间乘积、维护异或和似乎天经地义。但问题来了线段树处理的是“整个区间同时做操作”而这里不是整个区间。它有一个额外的条件——下标必须能被ki整除。这意味着每次更新的是区间里若干个离散的点这些点呈等差数列分布。线段树可以支持整段更新但不擅长支持“每隔几个位置取一个点”这种更新模式。再仔细想如果每次更新都是离散的点本质上就是“多点单点修改”那核心问题就变成了这些点的总数到底有多少会不会爆炸1.2 一次查询的完整效果我们不妨把一次查询的流程拆开。假设当前执行到第k次操作参数是[li, ri, k, vi]遍历闭区间[li, ri]内的所有下标筛出其中满足下标 % k 0的位置把这些位置的元素都乘以vi输出更新后整个数组所有元素的异或值。这里有一个容易被忽略的细节它操作的下标是“离散点”而不是连续区间。所以从数据结构层面看这题并不适合用“区间懒标记”的思路去套反而更适合直接定位到那些下标一个个处理。1.3 样例手动推演我构造一个简单的例子来验证理解。假设nums [1, 2, 3, 4, 5, 6] n 6下标按0开始编号。执行第一条查询[li1, ri5, k1, v2]。k1意味着区间里所有下标都能被 1 整除所以下标 1 到 5 全部乘 2数组变为[1, 4, 6, 8, 10, 12]全局异或和为1 ^ 4 ^ 6 ^ 8 ^ 10 ^ 12 13执行第二条查询[li0, ri4, k2, v3]。k2所以下标 0、2、4 这三个位置需要乘 3数组变为[3, 4, 18, 8, 30, 12]全局异或和为3 ^ 4 ^ 18 ^ 8 ^ 30 ^ 12 15执行第三条查询[li0, ri5, k3, v5]。k3所以下标 0、3 需要乘 5数组变为[15, 4, 18, 40, 30, 12]全局异或和为15 ^ 4 ^ 18 ^ 40 ^ 30 ^ 12 35整个推演过程就跟题意完全对上了每次不是区间整体乘而是挑出区间里下标满足特定模数的点来乘。2. 解题关键不是线段树而是调和级数复杂度2.1 暴力更新为什么可行如果这是普通的区间乘法那每次都要改一整段不用线段树根本不行。但这题妙就妙在第t条查询的k就是t所以第 1 次操作只动下标能被 1 整除的位置也就是全改一遍第 2 次操作只动下标能被 2 整除的位置第 3 次只动下标能被 3 整除的位置以此类推。那么总共的更新次数不是O(nq)而是n / 1 n / 2 n / 3 ... n / q这就是调和级数求和约等于n * (ln q C)其中C是欧拉常数大约 0.577。当n和q都取 10^5 时总更新次数大约是10^5 * (ln 10^5 0.577) ≈ 10^5 * 12.1 ≈ 1.2 * 10^6120 万次操作对于 Go 语言来说完全可以在几十毫秒内跑完。这才是这题真正的题眼表面区间更新实际总更新次数是可控的。2.2 复杂度上限的推导更严谨一点第k次操作区间[li, ri]内满足下标 % k 0的位置数量最多是floor(ri / k) - floor((li - 1) / k)当li 0、ri n-1时这个值不超过ceil(n / k)。所以总更新次数一定小于Σ_{k1}^{q} ceil(n / k) ≈ n * H_q这里H_q是调和数。空间复杂度就是O(n)只需要一个数组存当前值再用一个变量维护全局异或。所以这个题的最优解其实就是“暴力”。但这个暴力是有理论依据的暴力不是盲目暴力。2.3 用异或增量公式维护全局答案每次更新一个位置传统做法是把整个数组重新异或一遍复杂度 O(n)。但这道题每次操作后都要输出全局异或所以必须想办法 O(1) 更新。异或有一个很好的性质a ^ b ^ b a意思是异或两次相同的数会相互抵消。因此如果某个位置原来的值是old更新后变成newVal那么全局异或的变化可以这样处理currentXor currentXor ^ old ^ newVal先异或old相当于把旧值从全局异或集合中删除再异或newVal相当于把新值加进去。一轮操作只需要一次异或和一次乘法非常高效。这个公式是整个实现的核心几乎所有算法题中的“异或维护集合”都基于这个原理。2.4 为什么差分在这里救不了场很多人会想到能不能用一个差分数组记录每个位置被乘了多少最后再累乘得到结果想法很好但行不通。差分数组能轻松处理“加法”因为加法对前缀和有线性关系。但乘法不同而且更关键的是最终要输出的是异或和不是累乘和。异或本身对乘法因子不具备分配律(a * x) ^ (b * y) ≠ x ^ y 的某种组合也就是说你没法通过“某个区间统一乘以同一个数”这种懒标记去快速更新全局异或。因为每个位置初始值不同乘同一个因子后旧值和新值的异或变化量也不同必须逐个位置算。所以老老实实访问每个被命中的下标恰恰是这个题唯一高效且正确的路线。3. Go 语言实现细节3.1 直接可用的主代码我用 Go 写了一个完整实现代码里包含快速输入输出和核心更新逻辑package main import ( bufio fmt os strconv strings ) func main() { in : bufio.NewScanner(os.Stdin) in.Buffer(make([]byte, 1024*1024), 1024*1024) out : bufio.NewWriter(os.Stdout) defer out.Flush() readInt : func() int { in.Scan() val, _ : strconv.Atoi(strings.TrimSpace(in.Text())) return val } n : readInt() nums : make([]int64, n) currentXor : int64(0) for i : 0; i n; i { nums[i] int64(readInt()) currentXor ^ nums[i] } q : readInt() for i : 0; i q; i { l : readInt() r : readInt() k : readInt() v : readInt() // 找到区间内第一个能被 k 整除的下标 start : (l k - 1) / k * k for pos : start; pos r; pos k { old : nums[pos] // 小优化旧值为0或乘数为1时乘积不变 if old 0 || v 1 { continue } newVal : old * int64(v) currentXor ^ old ^ newVal nums[pos] newVal } fmt.Fprintln(out, currentXor) } }这里我统一用int64处理数组元素因为普通int在 32 位环境下可能不够用。currentXor也声明成int64保证异或结果不丢失高位。3.2 起始下标的定位与小优化代码里最关键的一行是start : (l k - 1) / k * k这是用来找闭区间[l, r]内第一个能被k整除的下标的。很多人会写成start : l / k * k这个写法在l不能被k整除时得到的是比l小的那个倍数而不是第一个大于等于l的倍数需要额外加判断。用(l k - 1) / k * k就省去了分支。找到起点之后每次步长就是k直接跳跃遍历for pos : start; pos r; pos k { ... }这样比“从 l 到 r 逐个判断pos % k 0”要快得多。尤其当k比较小的时候逐个判断会多出大量的取模运算而且区间越长浪费越明显。3.3 类型、溢出和负数问题如果题目没有特殊说明我默认nums中的元素和vi都在int64范围内且乘法结果不会溢出。这在大多数算法的数据范围约定里是成立的。如果题目明确说结果要对某个数取模那事情会麻烦一些因为异或和取模不兼容通常需要单独设计。但在这道题里我们直接按真实乘积处理。还有一个容易忽略的点如果nums里允许出现负数Go 的int64负数按二进制补码存异或运算依然按位进行结果解释成int64也是成立的。乘法虽然可能溢出但在二进制补码下溢出后的位模式仍然是一个确定的int64值只要题目保证按补码语义输出代码就是安全的。4. 常见问题与实测结果4.1 我在本地测试的耗时数据我造了一组规模拉满的数据n 100000q 100000k直接取查询编号1, 2, 3, ..., q。总更新次数大约是 120 万次。在普通笔记本上跑从读入到输出全部完成耗时不到 20 毫秒。这个性能已经非常宽裕了。但如果把数据改成故意卡人的情况k全部等于 1每次操作都会把整个数组重新乘一遍总更新次数是 10 的 10 次方级别代码基本跑不完。这也反过来证明题目在设计上一定保证了k与查询编号挂钩或者有类似的约束否则暴力更新策略不成立。4.2 边界用例我整理了几个常见边界情况可以对照自测场景结果区间内没有能被k整除的下标数组不变输出当前异或值k大于n一般没有点可更新直接输出原异或值v 1所有值不变可以跳过更新某个位置当前值是0乘任何数还是0跳过更新不影响结果l恰好能被k整除起点就是l本身l不能能被k整除起点是下一个比l大的倍数4.3 三个容易踩的坑第一个坑用fmt.Println逐行输出结果。当q是 10^5 级别时这会带来明显的 IO 开销。正确做法是用bufio.Writer先缓存最后统一刷新。第二个坑遍历时写成逐下标判断取模。也就是for pos : l; pos r; pos { if pos % k 0 { ... } }这个写法虽然结果正确但复杂度会变成O(q * n)即使k严格等于查询编号也压不住 10^5 的规模。必须用步进跳跃。第三个坑忽略old 0的情况。很多人觉得“旧值是 0 也要更新成 0反正没影响”于是每次都执行currentXor ^ old ^ newVal其实计算量差别很小但考虑到 120 万次更新里可能频繁出现 0加一个跳过条件能让代码更快也更清晰。唯一的例外是如果后面还有加法操作0 会被加出非零值那时候就绝对不能跳过了。5. 进一步思考如果此题的“Ⅰ”还有后续5.1 如果ki是步长而不是查询编号我前面分析的时候默认第k次操作中的k就是查询编号。但如果原题的ki表达的是“从li开始每隔ki个位置取一个点”那代码其实更简单只要把起点的计算方式改掉start : l然后遍历for pos : start; pos r; pos k { ... }这个变形下复杂度分析本质上没有区别只要第i次操作的k_i和下标范围合理总更新次数依然可能落在调和级数附近。如果真实题目是这种“步长”设定也希望大家能理解为什么我会在代码里保留pos k这条核心逻辑它是两种语义下共通的骨架。5.2 后续可能出现的区间加法、区间取模等变体既然标题里写了“Ⅰ”那大概率还有后续题目。我猜后续版本可能会引入两种变化第一种是每次操作不再只更新等差下标而是把整个区间都乘上vi这时候就必须上真正的线段树用懒标记维护区间乘法和全局异或。关键技巧是异或操作要用old ^ newVal的增量方式更新每个节点的值这时候节点里存的是区间异或和懒标记存的是乘法因子。第二种变化是加入区间异或查询也就是“每次操作后问你某个子区间的异或值”那就不再是维护全局异或就够的了需要线段树或者树状数组支持区间异或查询和区间乘法更新。但不管怎么变基本的增量异或公式都不会变currentXor currentXor ^ old ^ newVal这是所有异或维护题的底层逻辑。5.3 个人经验总结我在实际写这类题目的时候最大的体会就是看到“区间更新”先别急着套高级数据结构应该先算一算实际会被更新的点数。很多看起来复杂的题目只要更新次数总和是调和级数级别暴力反而就是最优解。另外用 Go 写算法题时输入输出优化和类型选择要尽早做。这题用int64和bufio基本不会因为性能翻车。如果你在刷题时发现自己的暴力超时建议先确认有没有漏掉old 0这类可以跳过的分支再检查是不是输出函数太慢最后才是考虑换数据结构。这几个排查顺序能解决绝大多数“不应该超时却超时”的问题。