Show problems as
Classic problem #3653MediumArrayDivide and ConquerSimulationPrefix Sum

XOR After Range Multiplication Queries I

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

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

Meter readings are given as nums, and a list of adjustments as queries. Each adjustment is [l, r, k, v] and multiplies, modulo 10^9 + 7, the readings at positions l, l + k, l + 2k and so on, taking every such position up to and including r.

Apply the adjustments in the order given, then return the bitwise exclusive-or of the whole list of readings.

Examples

Example 1

Input
nums = [13, 27, 41, 6, 19], queries = [[0, 4, 2, 3], [1, 3, 1, 7]]
Output
980

The first adjustment strides by two from position 0, so it triples the readings at 0, 2 and 4. The second strides by one from position 1 through 3, so it multiplies those three by seven. Combining the finished readings bitwise gives this.

Example 2

Input
nums = [5, 5, 5, 5, 5, 5], queries = [[0, 5, 3, 2]]
Output
0

Striding by three from position 0 reaches positions 0 and 3 only, doubling those two readings and leaving the other four alone.

Example 3

Input
nums = [2, 3, 5, 7, 11, 13, 17], queries = [[0, 6, 1, 1]]
Output
20

Multiplying by one changes nothing, so the answer is the readings combined as they came.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^9
  • 1 <= queries.length <= 1000
  • 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