Description
You are given an integer array nums of length n and a 2D integer array queries of size q, where queries[i] = [li, ri, ki, vi].
For each query, you must apply the following operations in order:
- Set
idx = li. - While
idx <= ri:- Update:
nums[idx] = (nums[idx] * vi) % (109 + 7). - Set
idx += ki.
- Update:
Return the bitwise XOR of all elements in nums after processing all queries.
Example 1:
Input: nums = [1,1,1], queries = [[0,2,1,4]]
Output: 4
Explanation:
- A single query
[0, 2, 1, 4]multiplies every element from index 0 through index 2 by 4. - The array changes from
[1, 1, 1]to[4, 4, 4]. - The XOR of all elements is
4 ^ 4 ^ 4 = 4.
Example 2:
Input: nums = [2,3,1,5,4], queries = [[1,4,2,3],[0,2,1,2]]
Output: 31
Explanation:
- The first query
[1, 4, 2, 3]multiplies the elements at indices 1 and 3 by 3, transforming the array to[2, 9, 1, 15, 4]. - The second query
[0, 2, 1, 2]multiplies the elements at indices 0, 1, and 2 by 2, resulting in[4, 18, 2, 15, 4]. - Finally, the XOR of all elements is
4 ^ 18 ^ 2 ^ 15 ^ 4 = 31.
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 1091 <= q == queries.length <= 105queries[i] = [li, ri, ki, vi]0 <= li <= ri < n1 <= ki <= n1 <= vi <= 105
Solutions
The solution optimizes query processing using square root decomposition: queries with step size k >= sqrt(n) are handled greedily, while queries with smaller step sizes are grouped by k and processed in bulk using a difference array combined with modular arithmetic. For each group, it uses a difference array to mark affected ranges, applies the modular inverse (computed via the pow helper function) to define range boundaries, then propagates multipliers through the array via prefix multiplication. This reduces time complexity from O(queries * n) to approximately O(n * sqrt(n)).
/**
* @param {number[]} nums
* @param {number[][]} queries
* @return {number}
*/
const MOD = 1_000_000_007n;
const pow = (x, y) => {
let res = 1n;
for (; y > 0n; y >>= 1n) {
if (y & 1n) {
res = (res * x) % MOD;
}
x = (x * x) % MOD;
}
return res;
};
var xorAfterQueries = function (nums, queries) {
const n = nums.length;
const T = Math.floor(Math.sqrt(n));
const groups = Array.from({ length: T }, () => []);
for (const [l, r, k, v] of queries) {
if (k < T) {
groups[k].push([l, r, BigInt(v)]);
continue;
}
for (let i = l; i <= r; i += k) {
nums[i] = Number((BigInt(nums[i]) * BigInt(v)) % MOD);
}
}
const dif = new BigInt64Array(n + T);
for (let k = 1; k < T; k++) {
if (groups[k].length === 0) {
continue;
}
dif.fill(1n);
for (let [l, r, v] of groups[k]) {
dif[l] = (dif[l] * BigInt(v)) % MOD;
const R = Math.floor((r - l) / k + 1) * k + l;
dif[R] = (dif[R] * pow(BigInt(v), MOD - 2n)) % MOD;
}
for (let i = k; i < n; i++) {
dif[i] = (dif[i] * dif[i - k]) % MOD;
}
for (let i = 0; i < n; i++) {
nums[i] = Number((BigInt(nums[i]) * dif[i]) % MOD);
}
}
return nums.reduce((acc, el) => acc ^ el, 0);
};