Segment Tree: Truy Vấn Giá Trị Lớn Nhất Đoạn & Cập Nhật

Buổi 27 — Segment Tree cơ bản Data-structures Trees
Points
40
AC Rate
0.0%
Time limit
1.5 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho mảng A gồm N số nguyên (1..N) và Q truy vấn thuộc hai loại:

  • 1 i v: Gán A[i] = v.
  • 2 L R: Tìm giá trị lớn nhất trong đoạn A[L..R].
Dữ liệu vào (Input)
  • Dòng 1: Hai số nguyên dương N và Q (1 ≤ N, Q ≤ 2 × 10^5).
  • Dòng 2: N số nguyên A[1..N] (-10^9 ≤ A[i] ≤ 10^9).
  • Q dòng tiếp theo: Mỗi dòng là một truy vấn loại 1 hoặc loại 2.
Dữ liệu ra (Output)
  • Với mỗi truy vấn loại 2, in ra giá trị lớn nhất trên đoạn [L, R].
Ví dụ mẫu
Sample Input 1
5 4
1 5 2 4 3
2 1 3
1 3 9
2 1 3
2 3 5
Sample Output 1
5
9
9
Draft saved