Truy Vấn Rừng 2D

Đ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 $n \times n$ gồm các ô trống (.) và cây (*). Hãy trả lời $q$ truy vấn, mỗi truy vấn hỏi có bao nhiêu cây trong hình chữ nhật từ hàng $r_{1}$ , cột $c_{1}$ đến hàng $r_{2}$ , cột $c_{2}$ (góc trên-trái đến góc dưới-phải).

Dữ liệu vào

Dòng đầu gồm hai số nguyên $n$ và $q$ .

$n$ dòng tiếp theo, mỗi dòng gồm $n$ ký tự . hoặc *.
$q$ dòng tiếp theo, mỗi dòng gồm bốn số nguyên $r_{1}$ , $c_{1}$ , $r_{2}$ , $c_{2}$ .

Dữ liệu ra

Với mỗi truy vấn, in số lượng cây trong hình chữ nhật đã cho.

Ràng buộc

$1 \leq n \leq 1000$
$1 \leq q \leq 2 \times 10^{5}$
$1 \leq r_{1} \leq r_{2} \leq n$
$1 \leq c_{1} \leq c_{2} \leq n$

Ví dụ

Input	Output	Giải thích
4 3 ... . . **** 2 2 3 4 3 1 3 1 1 1 2 2	3 1 2	Hình chữ nhật [2..3][2..4] có 3 cây, [3..3][1..1] có 1 cây, [1..2][1..2] có 2 cây.

Bình luận

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