[解题纪录] Love Song

题目

题目大意：

以题目的範例测试资料为例：

7 3abacaba1 32 51 7

解题思路：

例如範例中的歌曲abacaba, 可以先转成编号的array
a = [1, 2, 1, 3, 1, 2, 1] 接着回答每个问题时，需要频繁的计算subarray的值，
因此这里可以定义一个新的array表示方式，b[i] = sum[a[0] - a[i]]，这样会比较好计算

程式码：

// https://codeforces.com/problemset/problem/1539/B#include <iostream>#include <string>using namespace std;#define MAX_SIZE (int)(1e6+10)int main(){    int n, q, strNum[MAX_SIZE];    string str;    cin >> n >> q;    cin >> str;    strNum[0] = 0;    int strSize = str.size();    for (int i = 1; i <= strSize; i++) {        strNum[i] = strNum[i-1] + str[i-1] - 'a' + 1;    }    int l, r;    for (int i = 0; i < q; i++) {        cin >> l >> r;        cout << strNum[r] - strNum[l-1] << endl;    }    return 0;}