Truy vấn Rừng II

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một lưới ô vuông kích thước $n \times n$ . Mỗi ô vuông ban đầu là cây (*) hoặc ô trống (.). Bạn cần xử lý $q$ truy vấn thuộc hai loại:

Đổi trạng thái ô $(y, x)$ : nếu ô đang là cây thì chuyển thành trống, và ngược lại.
Đếm số cây trong hình chữ nhật con có góc trên trái $(y_{1}, x_{1})$ và góc dưới phải $(y_{2}, x_{2})$ .

Dòng đầu chứa hai số nguyên $n$ và $q$ : kích thước lưới và số truy vấn.

$n$ dòng tiếp theo, mỗi dòng chứa xâu $n$ ký tự mô tả lưới. Ký tự * là cây, . là ô trống.
$q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn:
1 y x — đổi trạng thái ô $(y, x)$
2 y1 x1 y2 x2 — đếm số cây trong hình chữ nhật từ $(y_{1}, x_{1})$ đến $(y_{2}, x_{2})$

Với mỗi truy vấn loại 2, in ra số cây trong hình chữ nhật tương ứng.

Input	Output	Giải thích
3 4 .. . .* 2 1 1 3 3 1 2 2 2 1 1 3 3 2 2 2 3 3	5 6 4	Ban đầu có 5 cây. Sau khi đổi ô (2,2) từ trống thành cây, toàn lưới có 6 cây. Hình chữ nhật (2,2)-(3,3) chứa 4 cây.
2 3 . . 2 1 1 2 2 1 1 2 2 1 1 2 2	2 3	Ban đầu có 2 cây trên đường chéo. Sau khi đổi ô (1,2) thành cây, toàn lưới có 3 cây.

Bình luận

Không có bình luận tại thời điểm này.