LeetCode 每日一题笔记

0. 前言

• 日期：2026.04.08
• 题目：3653.区间乘法查询后的异或一
• 难度：中等
• 标签：数组、模拟、数学、暴力遍历（题目标了分治但本题数据小，暴力可过）

---

1. 题目理解

问题描述

给你一个数组 nums 和一组查询 queries。 每个查询格式：[l, r, k, v]

操作规则：

1. 从下标 l 开始
2. 每次 +=k 跳步
3. 只要下标 ≤ r，就执行： nums[idx] = nums[idx] * v % MOD
4. 所有查询执行完，返回数组全部元素异或结果

示例

输入：

• nums = [1,1,1]
• queries = [[0,2,1,4]]

执行： 0 → 1 → 2 都 ×4 → [4,4,4] 异或：4 ^ 4 ^ 4 = 4

---

2. 解题思路

核心观察

1. 题目操作非常明确：按步长跳着乘
2. 数据范围不大：直接模拟遍历即可 AC，不需要线段树/分块
3. 必须取模：MOD = 1e9+7
4. 最后异或所有元素输出答案

暴力模拟思路（最直观、最稳）

• 遍历每一条查询
• 从 l 开始，按 step=k 跳着遍历到 r
• 每个位置都做 nums[i] = nums[i] * v % MOD
• 全部操作结束后，遍历数组求整体异或

算法步骤

1. 遍历所有查询
2. 对每个查询：l, r, step, val
3. idx 从 l 开始，每次 += step，直到 > r
4. 对每个 idx：nums[idx] = nums[idx] * val % MOD
5. 全部查询结束，遍历数组求异或，返回结果

---

3. 代码实现

package com.sheeta1998.lec.lc3600_lc3699.lc3653;

class lc3600_lc3699.lc3660.Solution {
    final int MOD = 1000000007;

    public int xorAfterQueries(int[] nums, int[][] queries) {
        // 处理每一条查询
        for (int[] q : queries) {
            int l = q[0];
            int r = q[1];
            int step = q[2];
            int v = q[3];

            // 按 step 跳着更新
            for (int idx = l; idx <= r; idx += step) {
                // 强转 long 防止 int 溢出
                nums[idx] = (int) ((long) nums[idx] * v % MOD);
            }
        }

        // 计算全部异或
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        return xor;
    }
}

---

4. 代码优化说明

1. 把 while 改成 for：更简洁、更安全、不易死循环
2. 强转 long 再取模：避免 int 相乘溢出
3. 增强 for 遍历查询：代码更清爽
4. 异或从 0 开始：不用处理边界（0 异或任何数 = 自身）

---

5. 复杂度分析

• 时间复杂度： O(q * 平均每个查询更新的数量 + n) 本题数据小，暴力完全能过。

• 空间复杂度： O(1)，只使用了几个临时变量

---

6. 总结

为什么不能用更高级算法（分治/线段树）？

• 因为步长 k 不固定，每个查询跳的位置不规则
• 无法用区间批量更新，只能逐个位置更新
• 所以本题 模拟就是最优解

本题核心要点

1. 按步长跳着更新：idx += k
2. 每次乘法必须取模：1e9+7
3. 乘法要转 long：防止 int 溢出
4. 最后整体异或输出答案
5. 直接模拟即可 AC，不需要复杂数据结构