思路

• 对于任意合法的 $i<j<k$，有

• 因此每个 “$red$” 子序列只和其首尾位置相关：权值为 $2\,(k-i)$。

• 令在位置 $j$ 取字母 $e$。设

  • $R_L(j)$：所有在 $j$ 左侧的 $r$ 的位置集合；
  • $D_R(j)$：所有在 $j$ 右侧的 $d$ 的位置集合。

• 则以该 $j$ 为中间字母的总贡献为：

• 只需维护：

  • 前缀：到每个位置为止的 $r$ 的个数与下标和；
  • 后缀：从每个位置之后的 $d$ 的个数与下标和。

• 枚举所有为 $e$ 的位置 $j$，用上式累加。时间复杂度 $O(n)$，空间复杂度 $O(n)$。使用 $64$ 位整型保存答案。

C++

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	string s;
	if (!(cin >> n)) return 0;
	cin >> s; // 字符串只含 r/e/d

	// 采用 1-based 下标进行计算，便于套用公式
	vector<long long> preRcnt(n + 1, 0), preRsum(n + 1, 0);
	for (int i = 1; i <= n; ++i) {
		preRcnt[i] = preRcnt[i - 1] + (s[i - 1] == 'r');
		preRsum[i] = preRsum[i - 1] + ((s[i - 1] == 'r') ? i : 0);
	}

	vector<long long> sufDcnt(n + 2, 0), sufDsum(n + 2, 0);
	for (int i = n; i >= 1; --i) {
		sufDcnt[i] = sufDcnt[i + 1] + (s[i - 1] == 'd');
		sufDsum[i] = sufDsum[i + 1] + ((s[i - 1] == 'd') ? i : 0);
	}

	long long ans = 0;
	for (int j = 1; j <= n; ++j) {
		if (s[j - 1] == 'e') {
			// 按推导公式累加贡献：2 * ( |R_L| * sum(D_R) - |D_R| * sum(R_L) )
			ans += 2LL * (preRcnt[j] * sufDsum[j] - sufDcnt[j] * preRsum[j]);
		}
	}

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

Python

import sys

data = sys.stdin.read().strip().split()
if not data:
    sys.exit(0)

n = int(data[0])
s = data[1].strip()

# 使用 1-based 下标便于直接套用公式
preRcnt = [0] * (n + 1)
preRsum = [0] * (n + 1)
for i in range(1, n + 1):
    preRcnt[i] = preRcnt[i - 1] + (1 if s[i - 1] == 'r' else 0)
    preRsum[i] = preRsum[i - 1] + (i if s[i - 1] == 'r' else 0)

sufDcnt = [0] * (n + 2)
sufDsum = [0] * (n + 2)
for i in range(n, 0, -1):
    sufDcnt[i] = sufDcnt[i + 1] + (1 if s[i - 1] == 'd' else 0)
    sufDsum[i] = sufDsum[i + 1] + (i if s[i - 1] == 'd' else 0)

ans = 0
for j in range(1, n + 1):
    if s[j - 1] == 'e':
        # 2 * ( |R_L| * sum(D_R) - |D_R| * sum(R_L) )
        ans += 2 * (preRcnt[j] * sufDsum[j] - sufDcnt[j] * preRsum[j])

print(ans)

Java

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line1 = br.readLine();
		if (line1 == null || line1.trim().isEmpty()) return;
		int n = Integer.parseInt(line1.trim());
		String s = br.readLine().trim(); // 字符串只含 r/e/d

		// 使用 1-based 下标
		long[] preRcnt = new long[n + 1];
		long[] preRsum = new long[n + 1];
		for (int i = 1; i <= n; i++) {
			preRcnt[i] = preRcnt[i - 1] + (s.charAt(i - 1) == 'r' ? 1 : 0);
			preRsum[i] = preRsum[i - 1] + (s.charAt(i - 1) == 'r' ? i : 0);
		}

		long[] sufDcnt = new long[n + 2];
		long[] sufDsum = new long[n + 2];
		for (int i = n; i >= 1; i--) {
			sufDcnt[i] = sufDcnt[i + 1] + (s.charAt(i - 1) == 'd' ? 1 : 0);
			sufDsum[i] = sufDsum[i + 1] + (s.charAt(i - 1) == 'd' ? i : 0);
		}

		long ans = 0;
		for (int j = 1; j <= n; j++) {
			if (s.charAt(j - 1) == 'e') {
				// 2 * ( |R_L| * sum(D_R) - |D_R| * sum(R_L) )
				ans += 2L * (preRcnt[j] * sufDsum[j] - sufDcnt[j] * preRsum[j]);
			}
		}

		System.out.println(ans);
	}
}

题目内容

小红有一个长度为 $n$ 的字符串 $s=s_1,s_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_1s_2s_4$ 权值为 $|1-2|+|1-4|+|2-4|=6$ 。

样例2

输入

7
redeeed

输出

52