Dynamic Range GCD

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 gcd (of absolute values; gcd(0,x)=|x|) 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 gcd (of absolute values; gcd(0,x)=|x|).

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

1
2
1

1 2
7
U 1 -5
Q 1 1

5

Read the Editorial