Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Large steps visit few indices, while small steps can affect long progressions. Split queries near sqrt(n): apply large-step queries directly and batch queries with the same small step using a multiplicative difference array along each residue class.

Approach

Let B = floor(sqrt(n)). Python groups steps at most B and directly updates larger steps; JavaScript groups steps below B and directly updates steps at least B. Either boundary choice preserves the square-root bound. JavaScript works on a BigInt copy, while Python updates nums.

For each grouped step, initialize a difference array to ones. Multiply by value at each query's left endpoint and by its modular inverse at the first progression index beyond the right endpoint: left + (floor((right - left) / step) + 1) * step, not necessarily right + 1.

Propagate products from index i - step to i, then multiply the factors into the working values. Each multiplier is positive and smaller than the prime modulus, so its inverse exists. Extra difference-array space accommodates cancellation beyond the array's end.

Process every group and XOR the final values. Multiplication commutes modulo the modulus, so regrouping queries does not change their effect.

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        sq = int(sqrt(n))
        mp = defaultdict(list)

        for l, r, k, v in queries:
            if k > sq:
                for i in range(l, r + 1, k):
                    nums[i] = (nums[i] * v) % MOD
            else:
                mp[k].append((l, r, v))
        
        for k in mp:
            dif = [1] * (n + k)
            for l, r, v in mp[k]:
                dif[l] = (dif[l] * v) % MOD
                rplus1 = l + ((r - l) // k + 1) * k # l + items * size of each step
                dif[rplus1] = (dif[rplus1] * pow(v, -1, MOD)) % MOD
            
            for i in range(k, n):
                dif[i] = (dif[i] * dif[i - k]) % MOD
            
            for i in range(n):
                nums[i] = (dif[i] * nums[i]) % MOD
        
        res = 0

        for x in nums: res ^= x

        return res

Complexity analysis

Let n = nums.length, q = queries.length, and B = floor(sqrt(n)). Grouped small-step difference products and direct large-step updates take O((n + q)B + q log MOD) time, including modular inverses, and O(n + q) auxiliary space. Each step-size group uses a fresh multiplicative difference array.