题解 | 舞萌时间到！

舞萌 DX 判定区间 dx 分总和（前缀和解法）

解题思路

这道题的核心是快速计算区间内的分数总和，由于查询次数较多（最多 1e4 次），如果每次查询都遍历区间计算会超时（时间复杂度 O (q*n)），因此需要用前缀和数组来优化。

步骤如下：

1. 建立映射关系：先明确每个判定字符对应的 dx 分数：P→3、p→2、G→1、g/m→0。
2. 构造前缀和数组：定义前缀和数组pre，其中pre[i]表示前i个字符（即字符串的第 1 到第 i 位）的 dx 分总和。这样，区间[l, r]的总和可以通过pre[r] - pre[l-1]快速计算。
3. 处理查询：对于每个查询的区间[l, r]，直接用前缀和数组的差值得到结果。

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

int main()
{
    string s;
    cin >> s;
    int len = s.size();
    vector<int> pre(len + 1, 0); // 前缀和数组,初始化为0
    int q;
    cin >> q;
    
    for (int i = 0; s[i]; i++)
    {
		int dx = 0; // 记录每一个字符的分数
        if (s[i] == 'P')
            dx = 3;
        else if (s[i] == 'p')
            dx = 2;
        else if (s[i] == 'G')
            dx = 1;
        // g和m默认dx=0
        pre[i + 1] = pre[i] + dx;
    }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        // 区间[l,r]对应前缀和的pre[r] - pre[l-1]
        int ans = pre[r] - pre[l - 1];
        cout << ans << endl;
    }
    return 0;
}

注意：前缀和数组：pre_sum的下标从 1 开始，pre_sum[0]=0，pre_sum[i]对应前i个字符的总和，避免了边界处理的麻烦。

算法：前缀和

时间复杂度分析

• 预处理前缀和：遍历字符串一次，时间复杂度为 O (n)（n 是字符串长度，最大 1e6）。
• 处理查询：每个查询是 O (1) 操作，q 次查询的时间复杂度为 O (q)（q 最大 1e4）。
• 总时间复杂度：O (n + q)，可以轻松通过题目限制的规模。

空间复杂度分析

• O (n)，用于存储前缀和数组。