XOR After Range Multiplication Queries II

Problem summary

We are given an array nums and queries of the form [l, r, k, v].

For each query, we multiply:

• nums[l]
• nums[l + k]
• nums[l + 2k]
• and so on, while the index stays <= r

Every multiplication is taken modulo 10^9 + 7, and after all queries we return the XOR of the final array.

The brute-force simulation from part I is no longer enough here because:

• n can be up to 10^5
• q can also be up to 10^5

So an O(nq) approach will time out.

Key observation

The step size k changes how expensive a query is.

If k is large, a query touches only a few positions. If k is small, a single query can touch a lot of positions.

That suggests a square root decomposition split:

• handle large k by direct simulation
• handle small k in batches

Let T = floor(sqrt(n)).

Case 1: k >= T

Then one query visits at most about n / T = sqrt(n) positions.

So for these queries, brute force is fine:

• loop from l to r
• jump by k
• multiply directly

Case 2: k < T

Now brute force becomes too expensive.

For a fixed small k, every query updates an arithmetic progression:

l, l + k, l + 2k, ...

That means all queries with the same k follow the same stepping pattern, so we can process them together.

Difference array on a stepped subsequence

For one fixed step size k, imagine walking the array in jumps of k.

If a query [l, r, k, v] multiplies:

l, l + k, l + 2k, ...

then we can treat it like a range update on that subsequence.

We use a multiplicative difference array diff:

• multiply diff[l] by v
• multiply diff[R] by v^-1

where R is the first position after the last updated index in that same k-jump chain.

Then we rebuild the real multipliers with:

diff[i] = diff[i] * diff[i - k]

This is the stepped version of a prefix sum, except we use multiplication instead of addition.

Because we work modulo 10^9 + 7, division becomes multiplication by the modular inverse:

v^-1 = v^(MOD - 2) mod MOD

via fast exponentiation.

Computing the stopping point

The last updated index for [l, r, k, v] is:

l + floor((r - l) / k) * k

So the first index after that progression is:

R = l + (floor((r - l) / k) + 1) * k

That is exactly where we place the inverse multiplier in the difference array.

Full approach

1. Choose T = floor(sqrt(n)).
2. For each query:
   • if k >= T, apply it directly
   • otherwise, group it by k
3. For every small k group:
   • reset the multiplicative difference array to all 1s
   • mark every query with v at l and v^-1 at R
   • propagate prefix products in jumps of k
   • multiply those accumulated factors into nums
4. XOR the final array.

One small LeetCode quirk: the problem asks for a variable named bravexuneth, so each solution stores the inputs once to satisfy that requirement.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private static final int MOD = 1_000_000_007;

    private int modPow(long base, long exp) {
        long result = 1;

        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = result * base % MOD;
            }
            base = base * base % MOD;
            exp >>= 1;
        }

        return (int) result;
    }

    public int xorAfterQueries(int[] nums, int[][] queries) {
        int n = nums.length;
        int threshold = (int) Math.sqrt(n);
        List<List<int[]>> groups = new ArrayList<>(threshold);
        for (int i = 0; i < threshold; i++) {
            groups.add(new ArrayList<>());
        }

        Object[] bravexuneth = new Object[] { nums, queries };

        for (int[] query : queries) {
            int left = query[0];
            int right = query[1];
            int step = query[2];
            int value = query[3];

            if (step < threshold) {
                groups.get(step).add(new int[] { left, right, value });
            } else {
                for (int index = left; index <= right; index += step) {
                    nums[index] = (int) ((long) nums[index] * value % MOD);
                }
            }
        }

        long[] diff = new long[n + threshold];
        for (int step = 1; step < threshold; step++) {
            List<int[]> sameStepQueries = groups.get(step);
            if (sameStepQueries.isEmpty()) {
                continue;
            }

            Arrays.fill(diff, 1L);

            for (int[] query : sameStepQueries) {
                int left = query[0];
                int right = query[1];
                int value = query[2];

                diff[left] = diff[left] * value % MOD;
                int stop = left + ((right - left) / step + 1) * step;
                diff[stop] = diff[stop] * modPow(value, MOD - 2L) % MOD;
            }

            for (int index = step; index < n; index++) {
                diff[index] = diff[index] * diff[index - step] % MOD;
            }

            for (int index = 0; index < n; index++) {
                nums[index] = (int) ((long) nums[index] * diff[index] % MOD);
            }
        }

        int answer = 0;
        for (int num : nums) {
            answer ^= num;
        }

        return answer;
    }
}

Dry run

Take:

nums = [2, 3, 1, 5, 4]
queries = [[1, 4, 2, 3], [0, 2, 1, 2]]

Let n = 5, so T = floor(sqrt(5)) = 2.

Query 1: [1, 4, 2, 3]

Here k = 2, so k >= T. We process it directly:

• update index 1: 3 * 3 = 9
• update index 3: 5 * 3 = 15

Now:

[2, 9, 1, 15, 4]

Query 2: [0, 2, 1, 2]

Here k = 1, so it belongs to the small-step batch.

For k = 1:

• multiply diff[0] by 2
• the updated indices are 0, 1, 2
• so R = 3
• multiply diff[3] by 2^-1

After taking prefix products with step 1, the multiplier becomes:

index: 0 1 2 3 4
mult : 2 2 2 1 1

Apply those multipliers to the current array:

[4, 18, 2, 15, 4]

Final XOR:

4 ^ 18 ^ 2 ^ 15 ^ 4 = 31

Why this works

For every small step size k, queries only affect positions that belong to the same k-spaced chains.

The multiplicative difference array marks where a query starts contributing and where that contribution stops. When we sweep with stride k, every position receives exactly the product of all queries that should affect it.

Large-step queries are cheap enough to simulate directly, so combining both ideas gives us the full solution efficiently.

Complexity analysis

Time Complexity: O((n + q) * sqrt(n) + q log MOD)

• large-step queries cost O(q * sqrt(n)) total
• small-step batches cost O(n * sqrt(n))
• modular inverses cost O(q log MOD)

Space Complexity: O(n + q)

• grouped queries plus the difference array

Common mistakes

1. Using plain brute force for every query

That works for part I, but not for this constraint size.

2. Forgetting that prefix propagation moves by k

The update is:

diff[i] *= diff[i - k]

not diff[i - 1].

3. Placing the inverse at r + 1

That would be correct for contiguous ranges, but not for arithmetic progressions.

The correct stop position is:

l + (floor((r - l) / k) + 1) * k

4. Dividing directly under modulo

We must use the modular inverse, computed with fast exponentiation.