Description

Red Cape Flying Cat has a very large character grid, and he wants to know how many distinct characters are in a given rectangular region.

The grid is 0-indexed. The cell at row r and column c is denoted as (r, c), where (0, 0) is the top-left corner. A rectangular region from (r1, c1) to (r2, c2) includes all cells (r, c) such that r1 <= r <= r2 and c1 <= c <= c2.

Since there are many queries, please help him write an efficient program to answer these questions.

Hint:
This is a Partial Judge Problem:
0. You will be provided 2 files below: 'main.c', 'function.h'. You should only upload your 'solver' function inside your '.c' file.
1. The 'main.c' file contains input, output, and function call, the 'function.h' file contains the declaration of 'solver' function, and your '.c' file should contain the implementation of 'solver' function.
2. You can compile multiple files by command, ex: 'gcc main.c function.h your_code.c', or create a project in your IDE.
3. Remember to include 'function.h'.
 

main.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <stdio.h>
#include "function.h"

#define MAXN 455
#define MAXM 455
#define MAXQ 2000005

char grid[MAXN][MAXM];
char *grid_ptr[MAXN];

int queries[MAXQ][4];
int *queries_ptr[MAXQ];

int results[MAXQ];
int *results_ptr[MAXQ];

int prefix[26][MAXN][MAXM];
int *prefix_row[26][MAXN];
int **prefix_ptr[26];

int main() {
    int n, m, q;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
        grid_ptr[i] = grid[i];
    }

    scanf("%d", &q);

    for (int i = 0; i < q; i++) {
        scanf("%d %d %d %d", &queries[i][0], &queries[i][1], &queries[i][2], &queries[i][3]);
        queries_ptr[i] = queries[i];
        results[i] = 0;
        results_ptr[i] = &results[i];
    }

    for (int c = 0; c < 26; c++) {
        for (int i = 0; i <= n; i++) {
            prefix_row[c][i] = prefix[c][i];
        }
        prefix_ptr[c] = prefix_row[c];
    }

    solver(grid_ptr, n, m, queries_ptr, results_ptr, q, prefix_ptr);

    for (int i = 0; i < q; i++) {
        printf("%d\n", results[i]);
    }

    return 0;
}

function.h

1
2
3
4
5
6

#ifndef FUNCTION_H
#define FUNCTION_H

void solver(char **s, int n, int m, int **queries, int **results, int q, int ***prefix);

#endif

It is recommended to use 2D prefix sum to solve this problem. Build a 2D prefix sum array for each character.

The expected time complexity is O(26 * N * M + 26 * Q).

Note: The 'prefix' parameter is a pre-allocated 3D array space. You may use it to build your 2D prefix sum, but it is not mandatory.

Input

The first line contains two integers N and M, representing the number of rows and columns of the grid.

The next N lines each contain a string of length M, consisting of only lowercase English letters.

The next line contains an integer Q, representing the number of queries.

The next Q lines each contain four integers r1, c1, r2, c2, representing a query for the rectangular region from (r1, c1) to (r2, c2). (0-indexed)

It is guaranteed that:
0. 1 <= N, M <= 450
1. 1 <= Q <= 2 * 10^6
2. 0 <= r1 <= r2 < N
3. 0 <= c1 <= c2 < M

Subtasks:
- Subtask 1 (20%, 2 testcases): N <= 150, M <= 150, Q <= 15000
- Subtask 2 (40%, 4 testcases): N = 1
- Subtask 3 (20%, 2 testcases): both r1 and c1=0 for all queries
- Subtask 4 (20%, 2 testcases): No additional constraints

Output

For each query, output one line containing the number of distinct characters in the rectangular region.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss