CSES - Dynamic Range Minimum Queries | Truy vấn min đoạn có cập nhật
Xem PDF
Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho 1 dãy có \(n\) số nguyên, nhiệm vụ của bạn là hãy xử lí \(q\) truy vấn của những loại sau đây:
- cập nhập giá trị ở vị trí \(k\) thành \(u\)
- tìm giá trị nhỏ nhất trong khoảng [\(a\),\(b\)]
Input
-
Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\): số lượng giá trị của dãy và try vấn.
-
Dòng thứ hai gồm \(n\) số nguyên \(x_1, x_2,...x_n\): những giá trị của dãy số.
-
Cuối cùng, có \(q\) dòng truy vấn. Mỗi dòng gồm 3 số nguyên: "\(1\, k\, u\)" hoặc "\(2\, a\, b\)".
Output
- In ra kết quả của các truy vấn loại 2.
Constraints
- \(1≤n,q≤2⋅10^5\)
- \(1≤x_i,u≤10^9\)
- \(1≤k≤n\)
- \(1≤a≤b≤n\)
Example
Test 1
Input
8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 2 3
2 1 4Output
2
1
3
Bình luận
.
???