Forest Queries

题目描述

给定一个大小为 n \times n 的网格表示森林地图。每个方格要么为空，要么包含一棵树。左上角方格的坐标为 (1,1)，右下角方格的坐标为 (n,n)。 你的任务是处理 q 个查询，形式为：给定森林中的一个矩形，矩形内有多少棵树？

输入格式

第一行包含两个整数 n 和 q：森林的大小和查询的数量。 接下来有 n 行描述森林。每行有 n 个字符：. 表示空方格，* 表示一棵树。 最后有 q 行描述查询。每行有四个整数 y_1, x_1, y_2, x_2，表示一个矩形的两个角。

输出格式

输出每个矩形内的树的数量。

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

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$

标签: CSES1652|区间查询

来源

CSES1652|区间查询