Nhiệt Độ Thấp Nhất

Buổi 27 — Segment Tree cơ bản
Points
11
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Trạm khí tượng ghi nhiệt độ tại N thành phố dọc đường quốc lộ. Số liệu của từng thành phố có thể được hiệu chỉnh lại. Hãy trả lời nhiệt độ thấp nhất trong một đoạn thành phố liên tiếp.

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q. Dòng thứ hai chứa N số nguyên a_1..a_N. Q dòng tiếp theo, mỗi dòng là một trong hai dạng:

  • 1 i x: gán a_i = x.
  • 2 l r: truy vấn trên đoạn [l, r].
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra giá trị nhỏ nhất trong a_l..a_r.

Ví dụ
Input Output
5 4\n1 9 6 3 7\n1 2 7\n1 4 3\n1 2 5\n2 1 2 1
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • 1 ≤ a_i, x ≤ 10^9
Draft saved