Segment Tree Practice 2

View as PDF

Submit solution

Points: 12
Time limit: 0.6s
Memory limit: 256M

Problem type

Given an array A of size N, support the Q of the following operations:

  1. Find the value and index of the smallest element from index l to index r. If there are multiple smallest elements, find the index of the earliest one.
  2. Update the element at index i to value x.


1 \le N, Q \le 2 \times 10^5

1 \le l \le r \le N

1 \le i \le N

1 \le A_i, x \le 10^9

Input Specification

The first line contains 2 integers N and Q.

The second line contains N integers A_1, A_2, \ldots, A_N, the initial elements of A.

The next Q lines are one of two forms:

  1. M l r representing the first operation.
  2. U i x representing the second operation.

Output Specification

For each type 1 operation output two integers, the minimum value and the leftmost index of that value in the given range.

Sample Input

5 5
6 3 3 2 4
M 2 4
M 2 3
U 2 6
M 1 2
M 1 3

Sample Output

2 4
3 2
6 1
3 3


There are no comments at the moment.