题目描述

给定长度为 n 的字符串 s（只包含字符 r、e、d），定义任何下标 i<j<k 且 s[i]='r', s[j]='e', s[k]='d' 的子序列 “red” 的权值为

|i-j| + |i-k| + |j-k|

计算所有这样的子序列权值之和。

解题思路

1. 化简权值公式
   当 i<j<k 时，|i-j|+|i-k|+|j-k| = (j−i)+(k−i)+(k−j) = 2*(k−i)。
   也就是说，每个 “r” 在位置 i 与每个 “d” 在位置 k 配对时，只要中间存在至少一个 “e”，就要累加 2*(k−i)×(中间 “e” 的个数)。

2. 在线统计

   • 维护一个数组 preE，preE[x] 表示位置 0..x 上出现的 ‘e’ 的总数。
   • 遍历字符串时：
     • 遇到 ‘r’（下标 i）时，更新：
       • cntR += 1
       • sumI += i
       • sumPE += preE[i]
       • sumIPI += i * preE[i]
     • 遇到 ‘d’（下标 k）时，先算出 k 之前的 ‘e’ 数量 E = preE[k−1]（k>0 时）
       然后所有已见过的 ‘r’ 对这次 ‘d’ 的贡献是

       contrib = E * (cntR * k - sumI)  -  (k * sumPE - sumIPI)
       

       最后答案累加 2 * contrib。

3. 时间和空间

   • 时间复杂度 O(n)，只遍历一次并做常数次计算。
   • 空间复杂度 O(n) 用于存 preE，可以优化到 O(1) 在线维护。

代码实现

Python

def calc_red_weight(s):
    n = len(s)
    # preE[i] = 0..i 范围内 'e' 的数量
    preE = [0] * n
    for i, ch in enumerate(s):
        preE[i] = preE[i-1] + (ch == 'e') if i else (ch == 'e')
    cntR = sumI = sumPE = sumIPI = 0
    ans = 0
    for k, ch in enumerate(s):
        if ch == 'r':
            # 记录一个 r 的信息
            cntR += 1
            sumI += k
            sumPE += preE[k]
            sumIPI += k * preE[k]
        elif ch == 'd':
            if cntR == 0: continue
            E = preE[k-1] if k > 0 else 0
            # M = cntR, A = sumI, B = sumPE, C = sumIPI
            M, A, B, C = cntR, sumI, sumPE, sumIPI
            # 组合贡献
            contrib = E * (M * k - A) - (k * B - C)
            ans += 2 * contrib
    return ans

# 读入输出
if __name__ == '__main__':
    import sys
    data = sys.stdin.read().split()
    n, s = int(data[0]), data[1].strip()
    print(calc_red_weight(s))

Java

import java.io.*;
import java.util.*;

public class Main {
    static long solve(String s) {
        int n = s.length();
        long[] preE = new long[n];
        for (int i = 0; i < n; i++) {
            preE[i] = (s.charAt(i) == 'e' ? 1 : 0) + (i > 0 ? preE[i-1] : 0);
        }
        long cntR = 0, sumI = 0, sumPE = 0, sumIPI = 0;
        long ans = 0;
        for (int k = 0; k < n; k++) {
            char c = s.charAt(k);
            if (c == 'r') {
                cntR++;
                sumI += k;
                sumPE += preE[k];
                sumIPI += k * preE[k];
            } else if (c == 'd') {
                if (cntR == 0) continue;
                long E = k > 0 ? preE[k-1] : 0;
                long M = cntR, A = sumI, B = sumPE, C = sumIPI;
                long contrib = E * (M * k - A) - (k * B - C);
                ans += 2 * contrib;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String s = br.readLine().trim();
        System.out.println(solve(s));
    }
}

C++

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

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

    int n;
    string s;
    cin >> n >> s;
    vector<long long> preE(n);
    for (int i = 0; i < n; i++) {
        preE[i] = (s[i] == 'e') + (i > 0 ? preE[i-1] : 0);
    }

    long long cntR = 0, sumI = 0, sumPE = 0, sumIPI = 0;
    long long ans = 0;
    for (int k = 0; k < n; k++) {
        if (s[k] == 'r') {
            cntR++;
            sumI += k;
            sumPE += preE[k];
            sumIPI += (long long)k * preE[k];
        } else if (s[k] == 'd') {
            if (cntR == 0) continue;
            long long E = k > 0 ? preE[k-1] : 0;
            long long M = cntR, A = sumI, B = sumPE, C = sumIPI;
            long long contrib = E * (M * k - A) - (k * B - C);
            ans += 2 * contrib;
        }
    }

    cout << ans << "\n";
    return 0;
}

题目内容

小红有一个长度为n的字符串$s=s_1s_2··.s_n$，她定义长度为$3$的子序列$s_is_js_k$的权值为$|i-j|+|i-k|+|j-k|$。

现在，小红希望你计算所有"$red$"子序列的权值之和。

如果字符串$t=$"$red$"可以通过删除字符串$s$中的若干

(可能为零或全部)元素得到，则字符串$t$是字符串$s$的"$red$"子序列。

输入描述

第一行输入一个整数$n(1≤n≤2×10^5)$，表示字符串的长度。

第二行输入一个长度为$n$，且只由'$r$'、'$e$'、'$d$'三个小写字母组成的字符串

输出描述

在一行上输出一个整数，代表所有"$red$"子序列的权值之和。

样例1

输入

4
reed

输出

12

说明

在该样例中，一共有两个不同的"red"子序列:

删除第二个字符得到的子序列$S_1S_3S_4$权值为

$|1-3|+|1-4|+|3-4|=6;$

删除第三个字符得到的子序列$S_1 S_2 S_4$权值为

$|1-2|+|1-4|+|2-4| =6$。

样例2

输入

7
redeeed

输出

52