3655. XOR After Range Multiplication Queries II

Array
Bit Manipulation
Math
Sqrt Decomposition

TIME

O((N + Q) * sqrt(N))

SPACE

O(N + Q)

Intuition

Two extreme approaches have tradeoffs:

Brute Force: Fast for large k (few elements), slow for small k (many elements)
Difference Array: Fast for small k (few unique values), slow for large k (many sweeps)

By splitting at sqrt(N), we get the best of both worlds.

Solution

Sqrt Decomposition

Let S = sqrt(N):

Large k (k >= S): Use brute force loop

Each query touches at most N/S = sqrt(N) elements
Total: O(Q × sqrt(N))

Small k (k < S): Use multiplicative difference array

Only S unique step sizes possible
Group queries by k, process each group with O(1) per query
Run S sweeps of size N
Total: O(N × sqrt(N))

Multiplicative Difference Array

For range multiplication with step k:

diff[l] *= v start multiplying at position l
diff[l + (steps+1)*k] *= v^(-1) cancel effect using modular inverse
Propagate: diff[i] = diff[i] * diff[i-k] for all i

Example: Query [l=0, r=2, k=1, v=4]

diff = [1, 1, 1, 1, 1]
diff[0] *= 4, diff[3] *= 4^(-1)
diff = [4, 1, 1, 4^(-1), 1]
After propagation: [4, 4, 4, 1, 1]

Modular Inverse

Using Fermat's Little Theorem:

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

Python: pow(v, -1, MOD) Java: Fast exponentiation

Complexity

Time: O((N + Q) × sqrt(N) + Q × log(MOD))
- Heavy queries: O(Q × sqrt(N))
- Light query placement: O(Q)
- Modular inverses: O(Q × log(MOD))
- Propagation sweeps: O(N × sqrt(N))
Space: O(N + Q)

Edge Cases

All queries have same k
k = 1 for all queries (worst case for brute force)
k = n for all queries (worst case for diff array)
Overlapping ranges with same k

Code

import math
from typing import List
from collections import defaultdict


class Solution:
    def xorAfterMultiplication(self, nums: List[int], queries: List[List[int]]) -> int:
        """
        3655. XOR After Range Multiplication Queries II
        Time: O((N + Q) * sqrt(N))
        Space: O(N + Q)
        
        Sqrt decomposition:
        - Large k (>= sqrt(n)): brute force, max sqrt(n) updates per query
        - Small k (< sqrt(n)): multiplicative difference array with modular inverse
        """
        bravexuneth = nums
        n = len(bravexuneth)
        MOD = 10**9 + 7
        limit = math.isqrt(n)

        # Group queries with small k for later processing
        lightK = defaultdict(list)

        for q in queries:
            l, r, k, v = q

            if k >= limit:
                # Large k: apply brute force
                for i in range(l, r + 1, k):
                    bravexuneth[i] = (bravexuneth[i] * v) % MOD
            else:
                # Small k: process later
                lightK[k].append(q)

        for k, query_list in lightK.items():
            # Process small queries grouped by step size k
            diff = [1] * n

            for q in query_list:
                l, r, _, v = q

                # Multiply starting position
                diff[l] = (diff[l] * v) % MOD

                # Cancel the multiplication using modular inverse
                steps = (r - l) // k
                nxt = l + (steps + 1) * k
                if nxt < n:
                    diff[nxt] = (diff[nxt] * pow(v, -1, MOD)) % MOD

            # Propagate the multipliers with a step size of k
            for i in range(n):
                if i >= k:
                    diff[i] = (diff[i] * diff[i - k]) % MOD
                bravexuneth[i] = (bravexuneth[i] * diff[i]) % MOD

        ans = 0
        for num in bravexuneth:
            ans ^= num

        return ans

import java.util.*;

/**
 * 3655. XOR After Range Multiplication Queries II
 * Time: O((N + Q) * sqrt(N))
 * Space: O(N + Q)
 * 
 * Sqrt decomposition:
 * - Large k (>= sqrt(n)): brute force, max sqrt(n) updates per query
 * - Small k (< sqrt(n)): multiplicative difference array with modular inverse
 */
class Solution {
    private static final long MOD = 1_000_000_007L;

    public int xorAfterMultiplication(int[] nums, int[][] queries) {
        int[] bravexuneth = nums;
        int n = bravexuneth.length;
        int limit = (int) Math.sqrt(n);

        // Group queries with small k
        Map<Integer, List<int[]>> lightK = new HashMap<>();

        for (int[] q : queries) {
            int l = q[0], r = q[1], k = q[2], v = q[3];

            if (k >= limit) {
                // Large k: brute force
                for (int i = l; i <= r; i += k) {
                    bravexuneth[i] = (int) ((bravexuneth[i] * (long) v) % MOD);
                }
            } else {
                // Small k: process later
                lightK.computeIfAbsent(k, x -> new ArrayList<>()).add(q);
            }
        }

        for (Map.Entry<Integer, List<int[]>> entry : lightK.entrySet()) {
            int k = entry.getKey();
            List<int[]> queryList = entry.getValue();

            long[] diff = new long[n];
            Arrays.fill(diff, 1L);

            for (int[] q : queryList) {
                int l = q[0], r = q[1], v = q[3];

                // Multiply starting position
                diff[l] = (diff[l] * v) % MOD;

                // Cancel using modular inverse
                int steps = (r - l) / k;
                int nxt = l + (steps + 1) * k;
                if (nxt < n) {
                    diff[nxt] = (diff[nxt] * modInverse(v)) % MOD;
                }
            }

            // Propagate multipliers with step size k
            for (int i = 0; i < n; i++) {
                if (i >= k) {
                    diff[i] = (diff[i] * diff[i - k]) % MOD;
                }
                bravexuneth[i] = (int) ((bravexuneth[i] * diff[i]) % MOD);
            }
        }

        int ans = 0;
        for (int num : bravexuneth) {
            ans ^= num;
        }

        return ans;
    }

    // Modular inverse using Fermat's Little Theorem: a^(-1) = a^(MOD-2) mod MOD
    private long modInverse(long a) {
        return modPow(a, MOD - 2);
    }

    private long modPow(long base, long exp) {
        long result = 1;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % MOD;
            }
            exp >>= 1;
            base = (base * base) % MOD;
        }
        return result;
    }
}