#CS1739. 森林查询 II

森林查询 II

题目背景

翻译自 CSES-1739 题。

题目描述

给定一个 n×nn×nn×n 的网格，表示森林的地图。每个格子要么为空，要么有一棵树。你的任务是处理 q 个查询，查询有以下两种类型：

• 修改一个格子的状态（从空格变为树，或者从树变为空格）。

• 查询一个矩形区域内有多少棵树。

输入格式

第一行包含两个整数 n 和 q：分别表示森林的大小和查询的数量。

接下来有 n 行，每行包含 n 个字符：. 代表空格， * 代表树。

然后有 q 行，每行描述一个查询。查询的格式有两种：

• 1 y x：表示将位置 (y,x) 的状态改变，若原本是树则变为空格，若原本是空格则变为树。

• 2 y1 x1 y2 x2：表示查询矩形区域 (y1,x1)(y_1,x_1)(y1​,x1​) 到 (y2,x2)(y_2,x_2)(y2​,x2​) 内有多少棵树。

输出格式

对于每个类型为 2 的查询，输出该矩形区域内的树的数量。

样例

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

3
4

说明/提示

$1 \leq n \leq 10$

$1 \leq q \leq 2 \cdot 10^5$

$1 \leq y,x \leq n$

1≤y1≤y2≤n1 \leq y_1 \leq y_2 \leq n1≤y1​≤y2​≤n；

1≤x1≤x2≤n1 \leq x_1 \leq x_2 \leq n1≤x1​≤x2​≤n。