Segment Tree: Truy Vấn Giá Trị Lớn Nhất Đoạn & Cập Nhật
Points
40
AC Rate
0.0%
Time limit
1.5 s
Memory limit
256M
Group
ds
Đề 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ánA[i] = v.2 L R: Tìm giá trị lớn nhất trong đoạnA[L..R].
Dữ liệu vào (Input)
- Dòng 1: Hai số nguyên dương
NvàQ(1 ≤ N, Q ≤ 2 × 10^5). - Dòng 2:
Nsố nguyênA[1..N](-10^9 ≤ A[i] ≤ 10^9). Qdòng tiếp theo: Mỗi dòng là một truy vấn loại1hoặc loại2.
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
Community Discussion