Forest Queries（森林查询）

题目来源

CSES Problem Set

---

题目描述

给定一个大小为

$n \times n$

的网格，表示一片森林地图。

每个格子要么是：

• . 表示 空地
• * 表示 一棵树

网格左上角坐标为：

$(1,1)$

右下角坐标为：

$(n,n)$

你需要处理 $q$ 个查询，每个查询给定一个矩形区域，询问该矩形中 ​树的数量​。

---

输入格式

第一行包含两个整数：

n q

表示森林的大小和查询次数。

1 ≤ n ≤ 1000
1 ≤ q ≤ 2 × 10^5

接下来 $n$ 行，每行包含 $n$ 个字符，描述森林地图：

.
*

其中：

• . 表示空地
• * 表示树

接下来 $q$ 行，每行包含四个整数：

y1 x1 y2 x2

表示查询的矩形区域左上角和右下角坐标：

$(y_1, x_1) \quad (y_2, x_2)$

保证：

$1 \le y_1 \le y_2 \le n$

$1 \le x_1 \le x_2 \le n$

---

输出格式

对于每个查询，输出一行一个整数，表示该矩形区域中 ​树的数量​。

---

样例输入

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

---

样例输出

3
1
2

---

样例说明

森林地图为：

.*..
*.**
**..
****

查询 1

2 2 3 4

矩形区域：

.**
*..

树的数量：

3

---

查询 2

3 1 3 1

区域：

*

树的数量：

1

---

查询 3

1 1 2 2

区域：

.*
*.

树的数量：

2

---

数据范围

$1 \le n \le 1000$

$1 \le q \le 2 \times 10^5$

---