思路:二维前缀和模板题

问题化简：给定一个矩阵，每次询问一个子矩阵中不同种类的字符串。

关键：字符串种类非常少，只有三种。所以我们暴力的开三个二维数组。每个二维数组用来记录一种字符串的二维前缀和。然后查询的时候分三次查询即可。

问题：二维前缀和是啥？？

可以参考：前缀和入门+练习

题目内容

在一片矩形勘探区域中，共有 $n$ 行 $m$ 列单元格，每个单元格内标注了三种矿物代号之一：x、y、z。定义某个子矩形区域的矿物种类数为该区域内实际出现过的不同矿物代号数量。现在给出完整标注和 $q$ 次询问，每次询问指定一个子矩形，请回答该子矩形的矿物种类数。约束：矩阵的行数 n 和列数 m 均不超过 500；询问次数 q 不超过 50000；每次询问的左上角为第 $r_1$ 行第 $c_1$ 列，右下角为第 $r_2$ 行第 $c_2$ 列，满足 $1 \le r_1 \le r_2 \le n$ 且 $1 \le c_1 \le c_2 \le m$。

输入描述

第一行包含两个正整数 n 和 m，分别表示勘探区域的行数和列数。接下来 n 行，每行包含 m 个用空格分隔的字符，每个字符为 x、y 或 z，表示对应单元格的矿物代号。接下来一行包含一个正整数 q，表示询问次数。接下来 q 行，每行包含四个正整数 r1, c1, r2, c2，表示一次询问的子矩形左上角位置为第 r1 行第 c1 列，右下角位置为第 r2 行第 c2 列。

输出描述

输出 q 行，每行一个整数，表示对应子矩形内实际出现的不同矿物代号数量。

样例1

输入

2 2
x y
z x
3
1 1 2 2
1 1 1 2
2 1 2 1

输出

3
2
1

说明

矩阵为 $2 \times 2$，四个格子依次为 x、y、z、x。

查询 1 1 2 2 覆盖整个矩阵，出现 x、y、z 三种矿物，因此答案为 3。

查询 1 1 1 2 覆盖第一行两个格子，只有 x 和 y，缺少 z，因此答案为 2。

查询 2 1 2 1 只覆盖左下角一个格子，该位置为 z，因此答案为 1。

样例2

输入

4 4
x x x x
x y y x
x y z x
x x x x
4
1 1 4 4
2 2 3 3
1 1 1 4
4 4 4 4

输出

3
2
1
1

说明

矩阵为 $4 \times 4$。

查询 1 1 4 4 覆盖整个矩阵，实际出现 x、y、z 三种矿物，答案为 3。

查询 2 2 3 3 覆盖中心 $2 \times 2$ 区域，包含 y 和 z，答案为 2。

查询 1 1 1 4 覆盖第一行，该行全为 x，答案为 1。

查询 4 4 4 4 只覆盖右下角一个格子，值为 x，答案为 1。

样例3

输入

1 1
x
2
1 1 1 1
1 1 1 1

输出

1
1

说明

勘探区域只有 $1 \times 1$，是题目允许的最小规模。唯一的格子矿物为 x。

两次查询都是 1 1 1 1，子矩形仍只包含这一个格子，所以实际出现的矿物种类数为 1。结果分别为 1 和 1。

样例4

输入

1 3
x y z
2
1 1 1 3
1 2 1 3

输出

3
2

说明

这是单行勘探区域，规模为 $1 \times 3$，格子依次为 x、y、z。

查询 1 1 1 3 覆盖整行，三种矿物全部出现，答案为 3。

查询 1 2 1 3 覆盖第 2 列到第 3 列，出现 y 和 z，缺少 x，答案为 2。