Show problems as
Classic problem #3655HardArrayDivide and ConquerPrefix Sum

XOR After Range Multiplication Queries II

Real-world version: Combining a Long Ledger After Stepped Scaling
Tracked in this browser only
Read XOR After Range Multiplication Queries II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A ledger holds entries nums. Each adjustment in queries is [l, r, k, v] and multiplies, modulo 10^9 + 7, the entries at positions l, l + k, l + 2k and onwards, as far as position r inclusive.

Both the ledger and the list of adjustments may run to a hundred thousand, so working every adjustment out entry by entry is far too slow.

Return the bitwise exclusive-or of the finished ledger.

Examples

Example 1

Input
nums = [1, 2, 4, 8, 16, 32], queries = [[1, 4, 2, 3]]
Output
43

The single adjustment strides by two from position 1 and stops at position 4, so it reaches positions 1 and 3 only, tripling those two entries and leaving the rest as they were.

Example 2

Input
nums = [5, 9], queries = [[0, 1, 2, 3], [1, 1, 1, 4]]
Output
43

The first adjustment strides by two from position 0, so it reaches position 0 alone and trebles the 5. The second multiplies position 1 by four.

Example 3

Input
nums = [6, 12, 18, 24, 30], queries = [[0, 4, 1, 1], [0, 4, 1, 1]]
Output
30

Both adjustments multiply by one, so the ledger is untouched.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= queries.length <= 10^5
  • queries[i].length == 4
  • 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1
  • 1 <= queries[i][2] <= nums.length
  • 1 <= queries[i][3] <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def xor_after_queries(nums: list[int], queries: list[list[int]]) -> int:
Java
public int xorAfterQueries(int[] nums, int[][] queries)

More on the same topics