Giám sát mức tối thiểu động

Bối cảnh và bài toán

Một hệ thống giám sát lưu n chỉ số theo thời gian. Một chỉ số có thể được hiệu chỉnh tại một vị trí, và người vận hành cần biết giá trị nhỏ nhất trên một đoạn bất kỳ sau các cập nhật.

Yêu cầu

Xử lý cập nhật điểm và truy vấn giá trị nhỏ nhất trên đoạn.

Input

• Dòng 1 chứa n q.
• Dòng 2 chứa mảng ban đầu.
• 1 k u: gán vị trí k bằng u.
• 2 a b: hỏi giá trị nhỏ nhất trên [a,b].

Output

In kết quả cho mỗi truy vấn loại 2.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• 1 <= a[i], u <= 10^9
• 1 <= k <= n
• 1 <= a <= b <= n

Chấm điểm

Ví dụ 1

Input

8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 2 3
2 1 4

Output

2
1
3

Giải thích. Sau cập nhật, min trên đoạn 1..4 tăng từ 2 lên 3.

Ví dụ 2

Input

4 4
9 7 8 6
2 1 4
1 4 10
2 2 4
2 4 4

Output

6
7
10

Giải thích. Truy vấn một phần tử cũng là một đoạn hợp lệ.

Thông tin bài tập

Nguồn: Phỏng theo CSES – Dynamic Range Minimum Queries.