Alice sở hữu một khu vườn táo thần kỳ hình chữ nhật kích thước \(N \times M\). Khu vườn được chia thành lưới ô vuông, các hàng được đánh số từ \(1\) đến \(N\), các cột được đánh số từ \(1\) đến \(M\). Tại ô đất ở hàng \(i\), cột \(j\), có một cây táo đang trĩu quả với số lượng là \(a_{i,j}\).
Để thu hoạch táo, Alice sử dụng một loại robot thông minh. Nếu robot được đặt tại vị trí \((u, v)\), nó có khả năng vươn tay hái toàn bộ số táo ở các ô \((x, y)\) thỏa mãn khoảng cách Manhattan đến vị trí đứng không vượt quá \(k\). Tức là:
Tuy nhiên, khu vườn này có phép thuật. Tại một số thời điểm bất kỳ, số lượng táo trên một cây tại vị trí \((x, y)\) có thể thay đổi đột ngột (do táo chín thêm hoặc bị rụng bớt).
Alice cần thực hiện một chuỗi các công việc gồm hai loại:
- Loại 1 (Thu hoạch): Đặt robot tại vị trí \((x, y)\) với tầm với \(k\), hãy tính tổng số táo mà robot có thể thu hoạch được.
- Loại 2 (Cập nhật): Số lượng táo tại ô \((x, y)\) thay đổi thành giá trị mới là \(val\).
Hãy giúp Alice quản lý khu vườn và tính toán sản lượng thu hoạch.
Input
Dữ liệu vào từ tệp văn bản APPLE.INP:
- Dòng đầu tiên chứa hai số nguyên dương \(N, M\) (\(N, M \le 1000\)).
- \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên dương. Số thứ \(j\) trên dòng thứ \(i\) là \(a_{i,j}\) (\(a_{i,j} \le 1000\)).
- Dòng tiếp theo chứa số nguyên dương \(Q\) (\(1 \le Q \le 10^4\)) là số lượng truy vấn.
-
\(Q\) dòng tiếp theo mô tả các truy vấn theo định dạng:
-
1 x y k: Truy vấn thu hoạch tại \((x, y)\) với tầm xa \(k\) (\(0 \le k \le 1000\)). -
2 x y val: Cập nhật số táo tại \((x, y)\) thành \(val\) (\(1 \le val \le 10^5\)). -
Dữ liệu đảm bảo toạ độ \((x, y)\) luôn hợp lệ (\(1 \le x \le N, 1 \le y \le M\)).
Output
Ghi ra tệp văn bản APPLE.OUT:
- Với mỗi truy vấn loại 1, in ra một dòng chứa tổng số táo thu hoạch được.
Example
Test 1
Input
3 3
1 1 1
1 10 1
1 1 1
3
1 2 2 1
2 2 2 5
1 2 2 1Output
14
9Note
Giải thích ví dụ:
-
Ban đầu lưới táo là:
\[ \begin{bmatrix} 1 & 1 & 1 \\ 1 & 10 & 1 \\ 1 & 1 & 1 \end{bmatrix} \] -
Truy vấn 1: Tại \((2, 2)\) với \(k=1\), các ô bị ảnh hưởng là \((2,2)\) (khoảng cách 0) và \((1,2), (3,2), (2,1), (2,3)\) (khoảng cách 1). Tổng = \(10 + 1 + 1 + 1 + 1 = 14\).
-
Truy vấn 2: Cập nhật ô \((2, 2)\) thành 5. Lưới mới:
\[ \begin{bmatrix} 1 & 1 & 1 \\ 1 & 5 & 1 \\ 1 & 1 & 1 \end{bmatrix} \] -
Truy vấn 3: Tại \((2, 2)\) với \(k=1\). Tổng = \(5 + 1 + 1 + 1 + 1 = 9\).
Scoring
- Subtask 1 (\(25\%\) số điểm): \(N, M \le 100\).
- Subtask 2 (\(25\%\) số điểm): \(k \le 20\).
- Subtask 3 (\(25\%\) số điểm): Không có truy vấn loại 2 (Cập nhật).
- Subtask 4 (\(25\%\) số điểm): Không có ràng buộc gì thêm.
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.