题解 | #舞萌时间到！#

问题的核心是多次查询一个静态数组（将字符串转化为分数数组）在不同区间 内的元素之和。由于数据量较大（字符串长度可达 ，询问次数可达 ），如果对于每次询问都暴力遍历区间求和，会导致超时。

这是一个经典的区间求和问题。

因此，最优的解决方案是使用前缀和算法。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int n = s.size();
    vector<ll> prefix(n + 1);
    prefix[0] = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'P') {
            prefix[i + 1] = prefix[i] + 3;
        } else if (s[i] == 'p') {
            prefix[i + 1] = prefix[i] + 2;
        } else if (s[i] == 'G') {
            prefix[i + 1] = prefix[i] + 1;
        } else {
            prefix[i + 1] = prefix[i];
        }
    }

    int q;
    cin >> q;

    while (q--) {
        int l, r;
        cin >> l >> r;
        ll ans = prefix[r] - prefix[l - 1];
        cout << ans << endl;
    }
}