Point Assign, Range Max

Difficulty: 1700 5000 ms 128 MB

segment-tree

Support U i v (assign a_i = v) and Q l r (print the maximum of a_l..r).

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

Output: one line per query.

Constraints:

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

Sample Tests

5 3
1 5 2 4 3
Q 1 5
U 2 0
Q 1 3

5
2

1 1
7
Q 1 1

7

Read the Editorial