Dốc Tăng Dần

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

Dọc theo một con đường có N điểm đo độ cao a_i. Một đoạn đường liên tiếp được gọi là 'không dốc xuống' nếu độ cao không giảm khi đi từ trái sang phải. Độ cao các điểm có thể được đo lại. Với mỗi truy vấn [l, r], tìm đoạn không dốc xuống dài nhất nằm trong [l, r].

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 độ dài lớn nhất của đoạn con liên tiếp không giảm trong a_l..a_r.

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