Description

Meet **Red Cape Flying Cat** - a magical feline who loves flying around with their bright red cape. Unfortunately, they just had their wisdom teeth removed and can't eat any solid food. The only thing they can consume is fruit juice!

Red Cape Flying Cat visits a long fruit stand where fruits are arranged in a row. Each position has one type of fruit (represented by lowercase letters 'a' to 'z'). Since their mouth still hurts, they can't speak clearly. The only way they can order is by pointing at two positions - the start and end of a range - and buying all fruits in between.

Now here's the problem: Red Cape Flying Cat is worried about drinking the same flavor over and over again. They want to know **how many different types of fruits** they'll get for each purchase, so they can decide if the juice will be diverse enough!

Since Red Cape Flying Cat will make many purchases (queries), please help them write an efficient program to answer these questions quickly.

Summarized_Question(if you are lazy to read the story)

Given a string S consisting only of lowercase English letters ('a' to 'z'), answer multiple queries efficiently.

Each query provides two integers L and R (0-based), representing the substring S[L..R] inclusive.

For each query, determine how many distinct characters appear in that substring.

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

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

#define MAXN 100005
#define MAXQ 100005

char str[MAXN];
int left[MAXQ], right[MAXQ];
int *left_ptr[MAXQ], *right_ptr[MAXQ];
int results[MAXQ];
int *res_ptr[MAXQ];

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

int main() {
    int q;
    scanf("%s", str);

    int len = 0;
    while (str[len] != '\0') len++;

    scanf("%d", &q);

    for (int i = 0; i < q; i++) {
        scanf("%d %d", &left[i], &right[i]);
        left_ptr[i] = &left[i];
        right_ptr[i] = &right[i];
        results[i] = 0;
        res_ptr[i] = &results[i];
    }

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

    solver(str, len, left_ptr, right_ptr, res_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 len, int **left, int **right, int **results, int q, int **prefix);

#endif

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

The expected time complexity is O(26 * |S| + 26 * Q).

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

Input

The first line contains a string S, consisting of only lowercase English letters.

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

The next Q lines each contain two integers L and R, representing a query for the range [L, R]. (0-indexed)

It is guaranteed that:
0. 1 <= |S| <= 10^5
1. 1 <= Q <= 10^5
2. 0 <= L <= R < |S|

Output

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

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss