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

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

구간합 문제.

문제 접근

구간 내에 문자 $\alpha$가 몇번 나오는지는 구간합과 유사한 방식으로

구할 수 있기 때문에, 구간합으로 접근한다.

$|S|\cdot 26$의 배열이 필요했다.

길이에 포함된 인덱스마다 알파벳이 몇 개 나왔는지 세야했다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

string s;
int q,l,r;
char c;
int arr[200000][26];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    memset(arr,0,sizeof(arr));
    cin >> s >> q;
    arr[0][s[0]-'a']++;
    for(int i=1;i<s.length();i++) for(int j=0;j<26;j++){
        if(s[i]-'a'==j) arr[i][j]=arr[i-1][j]+1;
        else arr[i][j]=arr[i-1][j];
    }
    while(q--){
        cin >> c >> l >> r;
        if(l==0) cout << arr[r][c-'a'];
        else cout << arr[r][c-'a']-arr[l-1][c-'a'];
        cout << '\n';
    }
    return 0;
}