统计数字出现的次数

输入一个长度不超过100000位的整数，接下来再输入n个询问，每个询问输入整数l, r, x。

对于每个询问，输出原数中从第l位数到第r位数中x出现的次数。

【数据范围】1≤l≤r≤10^5, 1≤n≤10^5, 0≤x≤9

输入格式
第一行包含一个整数n。
第二行是一个不超过100000位的整数。
接下来n行，每行包含三个整数l,r,x，每个数之间用一个空格隔。

输出格式
共n行，每行输出一个询问的结果。

输入：
2
1234234123
1 2 1
2 6 2

输出：
1
2

思路

1. 用常规方法会超时
2. 要用前缀和的思路
3. x不固定，所以要用10行的二维数组

#include<bits/stdc++.h>

using namespace std;

int a[10][100010];//第i（0~9）行代表数字i出现次数的前缀和

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int len = s.size();

    //初始化第0列
    for (int r = 0; r <= 9; r++) {
        a[r][0] = 0;
    }
    a[s[0] - '0'][0] = 1;

    //依次取得第1列开始的每个字符
    for (int i = 1; i < len; i++) {
        //将a的第i列修改成其前一列
        for (int r = 0; r <= 9; r++) {
            a[r][i] = a[r][i - 1];
        }
        a[s[i] - '0'][i]++;
    }

    for (int i = 1; i <= n; i++) {
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        // 注意：
        // 1. a[x][r - 1] - a[x][l - 1]的值不含第l-1列，所以要判断是否+1
        // 2. 用cout会超时
        printf("%d\n", a[x][r - 1] - a[x][l - 1] + (s[l - 1] == x + '0' ? 1 : 0));
    }
    return 0;
}