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