Bản Đồ Cao Nguyên

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

Một cao nguyên được chia thành lưới R hàng × C cột, ô (i, j) có độ cao h_{i,j}. Các nhà địa chất liên tục đo lại độ cao một ô và hỏi độ cao lớn nhất trong một vùng hình chữ nhật. Hãy dùng cây đoạn hai chiều.

Dữ liệu vào

Dòng đầu chứa R, C, Q. R dòng tiếp theo, mỗi dòng chứa C số h_{i,1..C}. Q dòng tiếp theo:

  • 1 x y v: đặt h_{x,y} = v.
  • 2 x1 y1 x2 y2: truy vấn hình chữ nhật.
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra độ cao lớn nhất trong các ô (i, j) với x1 ≤ i ≤ x2, y1 ≤ j ≤ y2.

Ví dụ
Input Output
5 5 4\n5 7 2 4 1\n8 3 7 5 7\n4 1 7 5 6\n5 9 4 7 7\n7 1 6 6 6\n2 2 4 2 5\n2 3 1 5 4\n2 4 3 4 3\n2 4 3 4 5 7\n9\n4\n7
Giới hạn
  • 1 ≤ R, C ≤ 500
  • 1 ≤ Q ≤ 10^5
  • 1 ≤ h, v ≤ 10^9
Draft saved