这个题目赛时的时候没有想到要以red中间的e开始计算，每次可以通过计算 ：当前为‘e’的元素前面的r的数量*后面d的数量，这样就得到了一个式子，然后经过一系列的化简就可以以o(1)计算出每一个结果，具体化简请看https://www.bilibili.com/video/BV1xh2qYgESd?p=3&vd_source=e52aee079d879cd3d2921a48f2de961f
具体代码如下：计算的时候注意代码细节即可 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
void solve() {
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    s = " " + s;
    vector<int> l(n+5,0);//记录前缀r的数量
    vector<int> r(n+5,0);//记录后缀d的数量
    vector<int> cnt_e(n+5,0);//'e'的前缀数量
    vector<int> star(n+5,0);//记录没有翻转时，字符串前i个e组成的“red”个数
    vector<int> pre_l(n+5,0);//'r'的数量前缀和的前缀和（s[i]==‘e’时转移）
    vector<int> pre_r(n+5,0);//'d'的后缀和的前缀和（s[i]==‘e’时转移）
    for (int i = 1; i <= n; ++i) {
        if(s[i] == 'r'){
            l[i] = l[i-1] + 1;
        } else{
            l[i] = l[i-1];
        }
    }
    for (int i = n; i >= 1; --i) {
        if(s[i] == 'd'){
            r[i] = r[i+1] + 1;
        } else{
            r[i] = r[i+1];
        }
    }
    for (int i = 1; i <= n; ++i) {
        if(s[i] == 'e'){
            cnt_e[i] = cnt_e[i-1] + 1;
            star[i] = star[i-1] + l[i-1]*r[i+1];
        } else{
            cnt_e[i] = cnt_e[i-1];
            star[i] = star[i-1];
        }
    }
    for (int i = 1; i <= n; ++i) {
        if(s[i] == 'e'){
            pre_l[i] = pre_l[i-1] + l[i];
            pre_r[i] = pre_r[i-1] + r[i];
        } else{
            pre_l[i] = pre_l[i-1];
            pre_r[i] = pre_r[i-1];
        }
    }
    while (q--){
        int l1,r1;
        cin>>l1>>r1;
        int x = l[l1-1] + l[r1];
        int y = r[r1+1] + r[l1];
        int ans = star[n] - (star[r1] - star[l1-1]);
        int t1 = (cnt_e[r1] - cnt_e[l1-1]) * ( x * y);
        int t2 = (star[r1] - star[l1-1]);
        int t3 = x * (pre_r[r1] - pre_r[l1-1]);
        int t4 = y * (pre_l[r1] - pre_l[l1-1]);
        ans = ans + (cnt_e[r1] - cnt_e[l1-1]) * ( x * y) + (star[r1] - star[l1-1])
                - x * (pre_r[r1] - pre_r[l1-1]) - y * (pre_l[r1] - pre_l[l1-1]);
        cout<<ans<<endl;
    }
}
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
除此之外，记录一下如何求一个子序列在原串里面出现的次数
对于dp[i][j],代表子序列长度为i的字串在长度为j的母串中出现的次数，这里长度都是从头算起的，而且遍历时，保持子串长度相同，先递增母串长度，母串最长时再增加一点子串长度重头开始计算母串。
初始化：当子串长度为0时，所有次数都是1，当母串长度为0时，所有次数都是0.
（1）如果子串的最后一个字母和母串的最后一个字母不同，说明新加的母串字母没有产生新的可能性，可以沿用该子串在较短母串的出现次数，所以dp(i)(j) = dp(i)(j-1)。
（2）如果子串的最后一个字母和母串的最后一个字母相同，说明新加的母串字母带来了新的可能性，这时dp(i)(j) = dp(i)(j-1) + dp(i-1)(j-1)。
代码： 
int numDistinct(string S, string T)
    {
        int dp[2000][2000]; //dp[i][j]:i表示子串长度，j表示母串长度
        //dp数组初始化
        for(int i=0;i<2000;i++)
        {
            for(int j=0;j<2000;j++)
            {
                dp[i][j]=0;
                dp[0][j]=1; //子串长度为0，即母串删去所有字符，出现1次
            }
        }
        
        int len_t = T.size();
        int len_s = S.size();
        for(int i=1;i<=len_t;i++)
        {
            for(int j=1;j<=len_s;j++)
            {
                if(T[i-1]!=S[j-1])
                    dp[i][j] = dp[i][j-1];
                else
                    dp[i][j] = dp[i][j-1] + dp[i-1][j-1]; //新增最后一个共同字符都定死到母串最后一个新字符的可能情况数
            }
        }
        return dp[len_t][len_s];
    }

牛客周赛 Round 63