思路:二维前缀和模板题

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

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

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

跟着塔子哥入门就完事了：前缀和入门+练习

代码

C++

#include<bits/stdc++.h>
using namespace std;
int n , m;
int a[3][505][505];
int get (int id , int x1 , int y1 , int x2 , int y2){ // 二维前缀和 - 查询子矩阵的和
    return a[id][x2][y2] - a[id][x1 - 1][y2] - a[id][x2][y1 - 1] + a[id][x1 - 1][y1 - 1] > 0; // 只要id这个字符串它在子矩阵中出现至少一次，那就算一次答案。
}
int main()
{
    cin >> n >>m;
    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= m ; j++){
            string x;
            cin >>x;
            for (int k = 0 ; k < 3 ; k++)
                a[k][i][j] = a[k][i - 1][j] + a[k][i][j - 1] - a[k][i - 1][j - 1]; // 二维前缀和转移
            if (x == "x") a[0][i][j]++;
            else if (x == "y") a[1][i][j]++;
            else a[2][i][j]++;
        }
    }
    int q;
    cin >> q;
    while (q--){
        int x1 , y1 , x2 , y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int res = 0;
        for (int i = 0 ; i < 3 ; i++){ // 查询 x , y , z 是否出现
            res += get(i , x1 , y1 , x2 , y2); 
        }
        cout << res << endl;
    }
    return 0;
}

Python

n, m = map(int, input().split())
a = [[[0] * 505 for _ in range(505)] for _ in range(3)]

def get(id, x1, y1, x2, y2):  # 二维前缀和 - 查询子矩阵的和
    return a[id][x2][y2] - a[id][x1 - 1][y2] - a[id][x2][y1 - 1] + a[id][x1 - 1][y1 - 1] > 0 # 只要id这个字符串它在子矩阵中出现至少一次，那就算一次答案。

for i in range(1, n + 1):
    arr = list(map(str , input().split()))
    for j in range(1, m + 1):
        x = arr[j - 1]
        for k in range(3):
            a[k][i][j] = a[k][i - 1][j] + a[k][i][j - 1] - a[k][i - 1][j - 1]  # 二维前缀和转移
        if x == "x":
            a[0][i][j] += 1
        elif x == "y":
            a[1][i][j] += 1
        else:
            a[2][i][j] += 1

q = int(input())
while q > 0:
    x1, y1, x2, y2 = map(int, input().split())
    res = 0
    for i in range(3):  # 查询 x, y, z 是否出现
        res += get(i, x1, y1, x2, y2)
    print(res)
    q -= 1

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][][] a = new int[3][505][505];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                String x = scanner.next();
                for (int k = 0; k < 3; k++) {
                    a[k][i][j] = a[k][i - 1][j] + a[k][i][j - 1] - a[k][i - 1][j - 1]; // 二维前缀和转移
                }
                if (x.equals("x")) {
                    a[0][i][j]++;
                } else if (x.equals("y")) {
                    a[1][i][j]++;
                } else {
                    a[2][i][j]++;
                }
            }
        }

        int q = scanner.nextInt();
        while (q-- > 0) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();
            int res = 0;
            for (int i = 0; i < 3; i++) { // 查询 x, y, z 是否出现
                res += get(a, i, x1, y1, x2, y2);
            }
            System.out.println(res);
        }
    }

    private static int get(int[][][] a, int id, int x1, int y1, int x2, int y2) {
        return a[id][x2][y2] - a[id][x1 - 1][y2] - a[id][x2][y1 - 1] + a[id][x1 - 1][y1 - 1] > 0 ? 1 : 0; // 只要id这个字符串它在子矩阵中出现至少一次，那就算一次答案。
    }
}

题目描述

给定一个字符串矩阵，字符串只含$x,y,z$ , 处理$q$次询问，每次询问一个子矩阵，输出这个子矩阵的本质不同字符串个数。

输入描述

第一行输入两个正整数$n,m$，代表矩阵的行数和列数

接下来的$n$行，每行输入$m$个字符串$s$ ($s \in \{x,y,z\}$ )

接下来的一行，输入一个正整数$q$，代表询问次数。

接下来的$q$行，每行输入四个正整数$x_1,y_1,x_2,y_2$，代表询问的子矩阵左上角为第$x_1$行第$y_1$列，右下角为第$x_2$行第$y_2$列。

$1 \leq n,m \leq 500$

$1 \leq q \leq 50000$

$1 \leq x_1 \leq x_2 \leq n$

$1 \leq y_1 \leq y_2 \leq m$

输出描述

输出$q$行，每行输出一个整数，代表子矩阵的本质不同字符串个数。

样例

输入

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

输出

1
3