5482. 森林查询（Forest Queries）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 给定一个大小为 $n imes n$ 的网格，表示一张森林地图。每个格子要么是空的，要么有一棵树。网格左上角坐标为 $(1,1)$，右下角坐标为 $(n,n)$。 你的任务是处理 $q$ 个查询：在给定的矩形区域内有多少棵树？ ## 输入格式 第一行两个整数 $n$ 和 $q$，表示森林大小和查询数量。 接下来 $n$ 行描述森林，每行包含 $n$ 个字符，`.` 表示空地，`*` 表示树。 接下来 $q$ 行描述查询，每行包含四个整数 $y_1$, $x_1$, $y_2$, $x_2$，表示矩形区域的对角格子坐标。 ## 输出格式 对于每个查询，输出对应矩形区域内的树木数量。 ## 输入输出样例 ### 输入 #1 ``` 4 3 .*.. *.** **.. **** 2 2 3 4 3 1 3 1 1 1 2 2 ``` ### 输出 #1 ``` 3 1 2 ``` ## 说明/提示 ### 数据规模与约定 - $1 \le n \le 1000$ - $1 \le q \le 2 \cdot 10^5$ - $1 \le y_1 \le y_2 \le n$ - $1 \le x_1 \le x_2 \le n$