Dynamic Range XOR

Difficulty: 1700 4000 ms 128 MB

segment-tree

Support two operations on an array: U i v assigns a_i = v, and Q l r prints the XOR (values are taken as given, two's complement not involved — inputs here are non-negative after |·|? No: XOR of possibly-negative is undefined, so inputs are made non-negative by the generator; treat them as plain integers) of a_l..r. Operations arrive interleaved, so precomputed prefixes go stale — a tree structure is required.

Input: the first line has N and Q; the second line has the initial array; each of the next Q lines is an operation.

Output: one line per Q operation with the requested XOR (values are taken as given, two's complement not involved — inputs here are non-negative after |·|? No: XOR of possibly-negative is undefined, so inputs are made non-negative by the generator; treat them as plain integers).

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• |values| ≤ 10⁶

Sample Tests

5 4
1 2 3 4 5
Q 2 4
U 3 10
Q 2 4
Q 1 5

5
12
8

1 2
7
U 1 -5
Q 1 1

5

Read the Editorial