백준 16139 인간-컴퓨터 상호작용

https://www.acmicpc.net/problem/16139

16139번: 인간-컴퓨터 상호작용

 

#include <iostream>

using namespace std;


int prefix[26][200001];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    string s;

    cin >> s;

    prefix[s[0] - 'a'][0] = 1;
    for (int i = 1; i < s.size(); i++) {
        for (int j = 0; j < 26; j++) {
            if (s[i] - 'a' == j) {
                prefix[j][i] = prefix[j][i - 1] + 1;
            } else {
                prefix[j][i] = prefix[j][i - 1];
            }
        }
    }

    int q;

    cin >> q;

    for (int qest = 0; qest < q; qest++) {

        char a;
        int l, r;

        cin >> a >> l >> r;

        if (l == 0) {
            cout << prefix[a - 'a'][r] << "\n";
        } else {
            cout << prefix[a - 'a'][r] - prefix[a - 'a'][l - 1] << "\n";
        }




    }


    return 0;
}

 

문자열의 최대 길이가 20만자나 되므로 전수조사를 했다간 시간초과가 난다.

 

20만자리의 문자열에 대해 각각의 알파벳의 개수의 누적합을 구한 후

주어지는 구간의 구간합을 계산한다.