e138. 種樹統計 - 花中程式設計挑戰系統

Content

給你一個 ***n * n* 的網格，代表一座森林的地圖。每個方格要麼是空的，要麼包含一棵樹。左上角方格的座標為 (1,1)，右下角方格的座標為 *(n,n)***。

你的任務是處理 q 個詢問，格式為：在森林指定的矩形區域內，總共有多少棵樹？

Input

第一行輸入包含兩個整數 n 和 q：代表森林的大小以及詢問的數量。
接下來有 n 行用來描述這座森林。每行包含 n 個字元：. 代表空地，* 代表一棵樹。
最後有 q 行用來描述詢問。每行包含四個整數 y1, x1, y2, x2，分別對應矩形區域的左上角與右下角座標。

Output

列印出每個矩形框內的樹木數量

Sample Input

4 3
.*..
*.**
**..
****
2 2 3 4
3 1 3 1
1 1 2 2

Sample Output

3
1
2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (1%): 1.0s , <10M
公開測資點#1 (66%): 1.0s , <1K
公開測資點#2 (33%): 1.0s , <10M

Hint ：

題目來源：https://cses.fi/problemset/task/1652/

Tags:

二維前綴和二維陣列

出處:

CSES Range_Queries [管理者：

benjaminshih (11104)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」

給你一個 n * n 的網格，代表一座森林的地圖。每個方格要麼是空的，要麼包含一棵樹。左上角方格的座標為 (1,1)，右下角方格的座標為 (n,n)。

你的任務是處理 q 個詢問，格式為：在森林指定的矩形區域內，總共有多少棵樹？

給你一個 ***n * n* 的網格，代表一座森林的地圖。每個方格要麼是空的，要麼包含一棵樹。左上角方格的座標為 (1,1)，右下角方格的座標為 *(n,n)***。