0922HardArrayDivide and ConquerPrefix Sum

Combining a Long Ledger After Stepped Scaling

Tracked in this browser only

Trains the technique from

LeetCode 3655XOR After Range Multiplication Queries II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def xor_after_queries(nums: list[int], queries: list[list[int]]) -> int:

Java

public int xorAfterQueries(int[] nums, int[][] queries)

The intended approach

Time O((n + q) * sqrt(n)) for a ledger of n entries and q adjustments.Space O(n) for the products and the open and close records of one stride at a time.

Multiplication does not care about order, so an entry's finished value is just its starting value times every multiplier that reaches it. That turns the whole thing into working out one product per position, and the adjustments may then be handled in whatever order suits. Split them by stride. An adjustment with a large stride touches few positions, at most the ledger length divided by the stride, so walking it outright is cheap. An adjustment with a small stride may touch many positions, but there are only so many small strides, so gather all the adjustments sharing a stride and handle that stride once. Within a stride, the positions split into chains, one per starting remainder, and each adjustment is a run of consecutive links on one chain. Note where each run opens and where it closes, walk every chain carrying a running product, multiplying in the multipliers that open and dividing out those that have closed. Dividing under a remainder means multiplying by the modular inverse, which exists because every multiplier is below the modulus and the modulus is prime. Splitting at the square root of the ledger length balances the two halves: large strides cost the square root per adjustment, and small strides cost the ledger length per stride.

Pythonentry point: xor_after_queries

def xor_after_queries(nums, queries):
    MOD = 1000000007
    n = len(nums)
    product = [1] * n
    cut = 1
    while cut * cut < n:
        cut += 1
    inverse = {}

    def inv(v):
        if v not in inverse:
            inverse[v] = pow(v, MOD - 2, MOD)
        return inverse[v]

    by_stride = {}
    for l, r, k, v in queries:
        if k > cut:
            at = l
            while at <= r:
                product[at] = product[at] * v % MOD
                at += k
        else:
            by_stride.setdefault(k, []).append((l, r, v))
    for k in by_stride:
        opens = {}
        closes = {}
        for l, r, v in by_stride[k]:
            last = l + (r - l) // k * k
            opens.setdefault(l, []).append(v)
            closes.setdefault(last + k, []).append(v)
        for start in range(k):
            running = 1
            at = start
            while at < n + k:
                if at in opens:
                    for v in opens[at]:
                        running = running * v % MOD
                if at in closes:
                    for v in closes[at]:
                        running = running * inv(v) % MOD
                if at < n:
                    product[at] = product[at] * running % MOD
                at += k
    total = 0
    for i in range(n):
        total ^= nums[i] * product[i] % MOD
    return total

The obvious version

Work each adjustment out directly, striding from its start and multiplying every position it reaches. Costs the number of positions touched per adjustment with no batching at all, which is fine at small sizes and hopeless at the declared ones.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_xor_after_queries(nums, queries):
    MOD = 1000000007
    values = list(nums)
    for query in queries:
        l = query[0]
        r = query[1]
        k = query[2]
        v = query[3]
        at = l
        while at <= r:
            values[at] = values[at] * v % MOD
            at += k
    total = 0
    for x in values:
        total ^= x
    return total

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in