LeetCode 每日一题笔记 日期：2026.04.09 题目：3655.区间乘法查询后的异或二

LeetCode 每日一题笔记0. 前言日期2026.04.09题目3655.区间乘法查询后的异或二难度困难标签数组 根号分治 乘法差分 快速幂1. 题目理解问题描述给你一个长度为 n 的整数数组 nums 和一个大小为 q 的二维整数数组 queries其中 queries[i] [li, ri, ki, vi]。对于每个查询需要按以下步骤依次执行操作设定 idx li。当 idx ri 时更新nums[idx] (nums[idx] * vi) % (10^9 7)。将 idx ki。在处理完所有查询后返回数组 nums 中所有元素的按位异或结果。示例输入 nums [1,1,1], queries [[0,2,1,4]]输出 4解释唯一的查询 [0, 2, 1, 4] 将下标 0 到下标 2 的每个元素乘以 4。数组从 [1, 1, 1] 变为 [4, 4, 4]。所有元素的异或为 4 ^ 4 ^ 4 4。2. 解题思路核心观察直接暴力处理所有查询时间复杂度过高需根据步长 k 的大小分治处理步长 k 较小时如 k √q查询覆盖的元素多但同余类集中适合用乘法差分 逆元批量处理步长 k 较大时如 k ≥ √q单次查询覆盖的元素少直接暴力更高效模运算下乘法的逆操作需用快速幂求逆元费马小定理因 MOD1e97 是质数阈值取 √q 可平衡两类操作的时间复杂度。算法步骤确定分块阈值B √q 1将查询按步长 k 分为小步长k B和大步长k ≥ B分组存储小步长查询将 k B 的查询按 k 分组处理大步长查询直接暴力遍历对每个符合条件的元素乘 vi 取模处理小步长查询对每个小 k再按l % k分为同余类步长 k 时起始位置模 k 相同的元素在同一序列对每个同余类若仅一个查询则直接暴力否则用乘法差分数组左端点位置乘 v右端点下一位乘 v 的逆元计算前缀积将结果应用到原数组计算最终异或遍历数组所有元素异或得到结果。3. 代码实现classSolution{privatestaticfinalintMOD1_000_000_007;publicintxorAfterQueries(int[]nums,int[][]queries){intnnums.length;intB(int)Math.sqrt(queries.length)1;Listint[][]groupsnewArrayList[B];Arrays.setAll(groups,_-newArrayList());for(int[]q:queries){intlq[0],rq[1],kq[2],vq[3];if(kB){groups[k].add(newint[]{l,r,v});}else{for(intil;ir;ik){nums[i](int)((long)nums[i]*v%MOD);}}}int[]diffnewint[n1];for(intk1;kB;k){Listint[]ggroups[k];if(g.isEmpty()){continue;}Listint[][]bucketsnewArrayList[k];Arrays.setAll(buckets,_-newArrayList());for(int[]t:g){buckets[t[0]%k].add(t);}for(intstart0;startk;start){Listint[]bucketbuckets[start];if(bucket.isEmpty()){continue;}if(bucket.size()1){int[]tbucket.get(0);intlt[0],rt[1];longvt[2];for(intil;ir;ik){nums[i](int)((long)nums[i]*v%MOD);}continue;}intm(n-start-1)/k1;Arrays.fill(diff,0,m,1);for(int[]t:bucket){intlt[0];longvt[2];diff[l/k](int)((long)diff[l/k]*v%MOD);intr(t[1]-start)/k1;if(rm){diff[r](int)((long)diff[r]*pow(v,MOD-2)%MOD);}}longmulD1;for(inti0;im;i){mulDmulD*diff[i]%MOD;intjstarti*k;nums[j](int)((long)nums[j]*mulD%MOD);}}}intans0;for(intx:nums){ans^x;}returnans;}privatelongpow(longx,intn){longres1;for(;n0;n/2){if(n%20){resres*x%MOD;}xx*x%MOD;}returnres;}}4. 代码优化说明优化点1全局复用差分数组仅创建一个全局差分数组diff每次处理小步长查询时重置前 m 位为 1避免重复创建数组极致节省内存。优化点2同余类单查询直接暴力当某个同余类的查询数仅为 1 时跳过乘法差分的复杂逻辑直接暴力处理减少差分开销。优化点3快速幂求逆元利用费马小定理通过快速幂计算v^(MOD-2) % MOD得到 v 的模逆元高效实现乘法差分的“撤销”操作。优化点4分块阈值平衡阈值取√q 1将小步长和大步长的时间复杂度均控制在可接受范围避免单一策略的极端情况。5. 复杂度分析时间复杂度O(qqnq)O(q\sqrt{q} n\sqrt{q})O(qq​nq​)大步长查询每个查询处理元素数为O(n/k)O(n/k)O(n/k)因kqk \sqrt{q}kq​总操作数为O(qq)O(q\sqrt{q})O(qq​)小步长查询最多q\sqrt{q}q​个不同 k每个 k 处理同余类的时间为O(n)O(n)O(n)总操作数为O(nq)O(n\sqrt{q})O(nq​)快速幂求逆元单次为O(log⁡MOD)O(\log MOD)O(logMOD)可忽略。空间复杂度O(nq)O(n \sqrt{q})O(nq​)差分数组O(n)O(n)O(n)分组存储最多q\sqrt{q}q​个组总空间为O(q)O(q)O(q)但分块后实际为O(q)O(\sqrt{q})O(q​)量级。6. 总结核心思路是根号分治根据步长 k 的大小选择不同策略平衡时间复杂度关键技巧小步长用乘法差分 逆元批量处理大步长直接暴力模运算下的乘法区间更新需结合逆元实现差分的“区间乘”效果本题是分治思想在数组操作中的经典应用重点考察对时间复杂度的平衡能力。关键点回顾根号分治的阈值取q\sqrt{q}q​平衡两类操作小步长按同余类分组乘法差分结合逆元实现区间乘大步长直接暴力因单次查询覆盖元素少最终结果为所有元素的异或需在所有查询处理完后计算。