Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each query updates an arithmetic progression of indices, not every index in its interval. The smaller constraints allow visiting those indices directly and applying every multiplier to the current values.

Approach

For a query [left, right, step, value], start at left and repeatedly add step while the index remains at most right. At each visited position, multiply the stored number by value and reduce modulo 1,000,000,007. Continue through all queries in order.

Finally XOR every updated array value and return the result. A right endpoint is included only when it lies on the query's progression. Overlapping queries naturally multiply the same entry more than once. Modulo reduction belongs to each updated number; the final aggregate is bitwise XOR, not an arithmetic sum or a modular product.

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        for l, r, k, v in queries:
            idx = l
            while idx <= r:
                nums[idx] = (nums[idx] * v) % (10**9 + 7)
                idx += k

        res = 0
        for x in nums:
            res ^= x

        return res

Complexity analysis

Let U = sum(floor((r-l)/step)+1) across all queries. Time: O(n + U). Auxiliary space: O(1) excluding the mutated input array.