当前位置：首页 > news >正文

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

news 2026/4/21 7:27:51

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），单次查询覆盖的元素少，直接暴力更高效；
模运算下乘法的逆操作需用快速幂求逆元（费马小定理，因 MOD=1e9+7 是质数）；
阈值取 √q 可平衡两类操作的时间复杂度。

算法步骤

确定分块阈值：B = √q + 1，将查询按步长 k 分为小步长（k < B）和大步长（k ≥ B）；
分组存储小步长查询：将 k < B 的查询按 k 分组；
处理大步长查询：直接暴力遍历，对每个符合条件的元素乘 vi 取模；
处理小步长查询：
- 对每个小 k，再按l % k分为同余类（步长 k 时，起始位置模 k 相同的元素在同一序列）；
- 对每个同余类，若仅一个查询则直接暴力，否则用乘法差分数组：
  - 左端点位置乘 v；
  - 右端点下一位乘 v 的逆元；
- 计算前缀积，将结果应用到原数组；
计算最终异或：遍历数组，所有元素异或得到结果。

3. 代码实现

classSolution{privatestaticfinalintMOD=1_000_000_007;publicintxorAfterQueries(int[]nums,int[][]queries){intn=nums.length;intB=(int)Math.sqrt(queries.length)+1;List<int[]>[]groups=newArrayList[B];Arrays.setAll(groups,_->newArrayList<>());for(int[]q:queries){intl=q[0],r=q[1],k=q[2],v=q[3];if(k<B){groups[k].add(newint[]{l,r,v});}else{for(inti=l;i<=r;i+=k){nums[i]=(int)((long)nums[i]*v%MOD);}}}int[]diff=newint[n+1];for(intk=1;k<B;k++){List<int[]>g=groups[k];if(g.isEmpty()){continue;}List<int[]>[]buckets=newArrayList[k];Arrays.setAll(buckets,_->newArrayList<>());for(int[]t:g){buckets[t[0]%k].add(t);}for(intstart=0;start<k;start++){List<int[]>bucket=buckets[start];if(bucket.isEmpty()){continue;}if(bucket.size()==1){int[]t=bucket.get(0);intl=t[0],r=t[1];longv=t[2];for(inti=l;i<=r;i+=k){nums[i]=(int)((long)nums[i]*v%MOD);}continue;}intm=(n-start-1)/k+1;Arrays.fill(diff,0,m,1);for(int[]t:bucket){intl=t[0];longv=t[2];diff[l/k]=(int)((long)diff[l/k]*v%MOD);intr=(t[1]-start)/k+1;if(r<m){diff[r]=(int)((long)diff[r]*pow(v,MOD-2)%MOD);}}longmulD=1;for(inti=0;i<m;i++){mulD=mulD*diff[i]%MOD;intj=start+i*k;nums[j]=(int)((long)nums[j]*mulD%MOD);}}}intans=0;for(intx:nums){ans^=x;}returnans;}privatelongpow(longx,intn){longres=1;for(;n>0;n/=2){if(n%2>0){res=res*x%MOD;}x=x*x%MOD;}returnres;}}

4. 代码优化说明

优化点1：全局复用差分数组

仅创建一个全局差分数组diff，每次处理小步长查询时重置前 m 位为 1，避免重复创建数组，极致节省内存。

优化点2：同余类单查询直接暴力

当某个同余类的查询数仅为 1 时，跳过乘法差分的复杂逻辑，直接暴力处理，减少差分开销。

优化点3：快速幂求逆元

利用费马小定理，通过快速幂计算v^(MOD-2) % MOD得到 v 的模逆元，高效实现乘法差分的“撤销”操作。

优化点4：分块阈值平衡

阈值取√q + 1，将小步长和大步长的时间复杂度均控制在可接受范围，避免单一策略的极端情况。

5. 复杂度分析

时间复杂度：O(qq+nq)O(q\sqrt{q} + n\sqrt{q})O(qq+nq)
- 大步长查询：每个查询处理元素数为O(n/k)O(n/k)O(n/k)，因k>qk > \sqrt{q}k>q，总操作数为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(n+q)O(n + \sqrt{q})O(n+q)
- 差分数组：O(n)O(n)O(n)；
- 分组存储：最多q\sqrt{q}q个组，总空间为O(q)O(q)O(q)但分块后实际为O(q)O(\sqrt{q})O(q)量级。