3655. XOR After Range Multiplication Queries II

/**
 * Problem: LeetCode 3655 - XOR After Range Multiplication Queries II
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

class Solution {
    private static final long MOD = 1_000_000_007L;

    public int xorAfterQueries(int[] nums, int[][] queries) {
        int n = nums.length;
        int B = Math.max(1, (int) Math.sqrt(n));

        @SuppressWarnings("unchecked")
        List<int[]>[] smallK = new ArrayList[B];

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

            if (k >= B) {
                for (int idx = l; idx <= r; idx += k) {
                    nums[idx] = (int) (((long) nums[idx] * v) % MOD);
                }
            } else {
                if (smallK[k] == null) {
                    smallK[k] = new ArrayList<>();
                }
                smallK[k].add(q);
            }
        }

        for (int k = 1; k < B; k++) {
            if (smallK[k] == null) continue;

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

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

                diff[l] = (diff[l] * v) % MOD;
                int steps = (r - l) / k;
                int next = l + (steps + 1) * k;
                long inv = modInverse(v, MOD);
                diff[next] = (diff[next] * inv) % MOD;
            }

            for (int i = 0; i < n; i++) {
                if (i >= k) {
                    diff[i] = (diff[i] * diff[i - k]) % MOD;
                }
                nums[i] = (int) (((long) nums[i] * diff[i]) % MOD);
            }
        }

        int xorSum = 0;
        for (int val : nums) {
            xorSum ^= val;
        }

        return xorSum;
    }

    private long modInverse(long base, long mod) {
        return power(base, mod - 2, mod);
    }

    private long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return res;
    }
}

"""
Problem: LeetCode 3655 - XOR After Range Multiplication Queries II
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
import math
from collections import defaultdict

class Solution:
    def xorAfterQueries(self, nums: list[int], queries: list[list[int]]) -> int:
        MOD = 1_000_000_007
        n = len(nums)
        B = max(1, int(math.isqrt(n)))
        
        small_k = defaultdict(list)
        
        for l, r, k, v in queries:
            if k >= B:
                for idx in range(l, r + 1, k):
                    nums[idx] = (nums[idx] * v) % MOD
            else:
                small_k[k].append((l, r, v))
                
        for k, q_list in small_k.items():
            diff = [1] * (n + k)
            for l, r, v in q_list:
                diff[l] = (diff[l] * v) % MOD
                steps = (r - l) // k
                nxt = l + (steps + 1) * k
                diff[nxt] = (diff[nxt] * pow(v, MOD - 2, MOD)) % MOD
                
            for i in range(n):
                if i >= k:
                    diff[i] = (diff[i] * diff[i - k]) % MOD
                nums[i] = (nums[i] * diff[i]) % MOD
                
        xor_sum = 0
        for val in nums:
            xor_sum ^= val

        return xor_sum

/**
 * Problem: LeetCode 3655 - XOR After Range Multiplication Queries II
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

class Solution {
private:
    static constexpr long long MOD = 1000000007LL;

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

    long long modInverse(long long base) {
        return power(base, MOD - 2);
    }

public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int B = max(1, (int)sqrt(n));

        vector<vector<vector<int>>> smallK(B);

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

            if (k >= B) {
                for (int idx = l; idx <= r; idx += k) {
                    nums[idx] = (int)((1LL * nums[idx] * v) % MOD);
                }
            } else {
                smallK[k].push_back(q);
            }
        }

        for (int k = 1; k < B; ++k) {
            if (smallK[k].empty()) continue;

            vector<long long> diff(n + k, 1);

            for (const auto& q : smallK[k]) {
                int l = q[0];
                int r = q[1];
                int v = q[3];

                diff[l] = (diff[l] * v) % MOD;
                int steps = (r - l) / k;
                int next = l + (steps + 1) * k;
                diff[next] = (diff[next] * modInverse(v)) % MOD;
            }

            for (int i = 0; i < n; ++i) {
                if (i >= k) {
                    diff[i] = (diff[i] * diff[i - k]) % MOD;
                }
                nums[i] = (int)((1LL * nums[i] * diff[i]) % MOD);
            }
        }

        int xorSum = 0;
        for (int val : nums) {
            xorSum ^= val;
        }

        return xorSum;
    }
};

/**
 * Problem: LeetCode 3655 - XOR After Range Multiplication Queries II
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number}
 */
var xorAfterQueries = function(nums, queries) {
    const MOD = 1000000007n;
    const n = nums.length;
    const B = Math.max(1, Math.floor(Math.sqrt(n)));

    const power = (base, exp) => {
        let res = 1n;
        let b = BigInt(base) % MOD;
        let e = BigInt(exp);
        while (e > 0n) {
            if (e & 1n) res = (res * b) % MOD;
            b = (b * b) % MOD;
            e >>= 1n;
        }
        return res;
    };

    const modInverse = (base) => power(base, MOD - 2n);

    const smallK = new Map();

    for (let i = 0; i < queries.length; i++) {
        const [l, r, k, v] = queries[i];
        if (k >= B) {
            const vBig = BigInt(v);
            for (let idx = l; idx <= r; idx += k) {
                nums[idx] = Number((BigInt(nums[idx]) * vBig) % MOD);
            }
        } else {
            if (!smallK.has(k)) smallK.set(k, []);
            smallK.get(k).push([l, r, v]);
        }
    }

    for (const [k, qList] of smallK.entries()) {
        const diff = new BigInt64Array(n + k);
        diff.fill(1n);

        for (let i = 0; i < qList.length; i++) {
            const [l, r, v] = qList[i];
            const vBig = BigInt(v);
            diff[l] = (diff[l] * vBig) % MOD;
            const steps = Math.floor((r - l) / k);
            const next = l + (steps + 1) * k;
            diff[next] = (diff[next] * modInverse(vBig)) % MOD;
        }

        for (let i = 0; i < n; i++) {
            if (i >= k) {
                diff[i] = (diff[i] * diff[i - k]) % MOD;
            }
            nums[i] = Number((BigInt(nums[i]) * diff[i]) % MOD);
        }
    }

    let xorSum = 0;
    for (let i = 0; i < n; i++) {
        xorSum ^= nums[i];
    }

    return xorSum;
};