小红的red计数

链接：https://ac.nowcoder.com/acm/contest/91592/E 来源：牛客网

1. 题目描述

小红拿到了一个字符串。她有若干次询问，每次询问：若翻转第l个字符到第r个字符对应的区间，该字符串有多少"red"子序列。子序列指按原串顺序取若干字母（可以不连续）形成的新字符串。如"rreedd"存在8个"red"子序列。请注意，每次询问后并不会真正翻转区间！

1.1 输入描述:

第一行输入两个正整数 $n,q$ 代表字符串长度和询问次数。第二行输入一个长度为 $n$ 的、仅由小写字母组成的字符串。接下来的 $q$ 行，每行输入两个正整数 $l,r$ ，代表一次询问。

$1 \leq n,q \leq10^5$ ， $1 \leq l,r \leq n$

1.2 输出描述:

输出q行，每行输出一个整数，代表询问的答案。

1.3 样例输入

6 2
rreedd
1 2
1 6

1.4 样例输出

8
0

2. 思路分析：

2.1 标签: 模拟 + 前缀和

2.2 解题思路

看到题目 $q$ 次询问，且 $q$ 最大为 $10^5$ ，首先最基本的判断就是 slove() 算法的复杂度一定在 $10^3$ 以内，但是 $n$ 的最大为 $10^5$ ，slove() 的算法最多为 $\sqrt{10^5}$ ，所以符合条件的算法并不多。(算法复杂度与时间的关系)

先想到本题的暴力做法，即通过 for()判断每个 $e$ 的左边有多少个 $r$ 、右边有多少个 $d$ ，通过从左往右预处理 $r$ 的前缀和、从右往左预处理 $d$ 的后缀和，可以把一般 $O(n^3)$ 的 slove() 优化为 $O(n)$ 的复杂度。

接下来考虑一般情况下答案的组成：

1 - r - l - n

设 $r$ 的前缀和为 $pre[]$ ( 遍历到 $i$ 前面有多少个 $r$ )， $d$ 的后缀和为 $suf[]$ (遍历到 $i$ 后面有多少个 $d$ )，字符串 $s$ 。其中， $1$ ~ $l-1$ 中的 $e$ 的贡献 $\sum_{i = 1} ^ {l - 1}[S_i =e]{pre[i] \times suf[i]}$ 和 $r 1$ ~ $n$ 中 $e$ 的贡献 $\sum_{i = r 1} ^ {n}[S_i =e]{pre[i] \times suf[i]}$ 并没有变，只需要重新计算 $r$ ~ $l$ 中 $e$ 的贡献再与前者相加即可，答案的正确性是显然的。

1 - l - e(i) - r - n

1 - r - e(i) - l - n

设 $e$ 的坐标为 $i$ ，要计算 $l$ ~ $r$ 中的贡献。对于 $l$ ~ $r$ 的每个 $e$ ，很显然都有 $pre[i] \times suf[i]$ 的贡献。 $e$ 左边的 $pre[i]$ 可拆为 $pre[l - 1]$ 和 $pre[r] - pre[i]$ (请注意 $l$ 、 $r$ 的位置实际并没有改变)； $e$ 右边的 $suf[i]$ 可拆为 $suf[r 1]$ 和 $suf[l] - suf[i]$ 。因此对于 $l$ ~ $r$ 中的 $e$ ，共有 $\sum_{i = l}^{r}[S_i =e]{(pre[l - 1] (pre[r] - pre[i])) \times (suf[r 1] (suf[l] - suf[i]))}$ 的贡献，因此我们可以得到如下的式子：

ans = \sum_{i = 1} ^ {l - 1}[S_i =e]{pre[i] \times suf[i]} \sum_{i = r 1} ^ {n}{pre[i] \times suf[i]} \\ ans = \sum_{i = l}^{r}[S_i =e]{(pre[l - 1] (pre[r] - pre[i])) \times (suf[r 1] (suf[l] - suf[i]))}

根据以上的式子，我们可以得到 $O(n \times q)$ 的做法：

while(q--)
{
	ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(i < l || i > r) ans += pre[i] * suf[i];
        else ans += (pre[l - 1] + (pre[r] - pre[i]) * (suf[r + 1] + (suf[l] - suf[i]))
    }
}

比赛时我也只想到这里，很显然是过不了的，拿到了 20% 的分。 $O(n)$ 不够，我们要考虑 $O(1)$ 的复杂度，也就是考虑答案能由一个公式直接推出来，这一点跟牛客之前的也是考察前缀和的 [奏绝](E-奏绝_牛客小白月赛93 (nowcoder.com)) 如出一辙。

对 $\sum_{i = 1} ^ {l - 1}[S_i =e]{pre[i] \times suf[i]} \sum_{i = r 1} ^ {n}[S_i =e]{pre[i] \times suf[i]}$ ，我们考虑预处理：用一个 $sum[]$ 维护 $red$ 数量的前缀和（表示遍历到 $i$ 时 $red$ 的数量），显然上式可以 $O(1)$ 地表示为 $sum[l-1] (sum[n] - sum[r])$ ，不可能更简。
对 $\sum_{i = l}^{r}[S_i =e]{((pre[l - 1] (pre[r] - pre[i])) \times (suf[r 1] (suf[l] - suf[i])))}$ 化简：

$\sum_{i = l}^{r}[S_i =e]{((pre[l - 1] (pre[r] - pre[i])) \times (suf[r 1] (suf[l] - suf[i])))} \\ \Leftrightarrow \\ \sum_{i = l}^{r}[S_i =e]{((pre[l - 1] pre[r] - pre[i]) \times (suf[r 1] suf[l] - suf[i]))}$

设定值 $x = pre[l - 1] pre[r],y = suf[r 1] suf[l]$ ，则有：

$\sum_{i = l}^{r}[S_i =e]{((x - pre[i]) \times (y - suf[i]))} \\ \Leftrightarrow \\ \sum_{i = l}^{r}[S_i =e](xy - (x \times suf[i] y \times pre[i]) pre[i] \times suf[i]) \\ \Leftrightarrow \\ \sum_{i = l}^{r}[S_i =e]xy - \sum_{i = l}^{r}[S_i =e](x \times suf[i] y \times pre[i]) \sum_{i = l}^{r}[S_i =e](pre[i] \times suf[i])$

对该式的三个部分进行分析：
1. $\sum_{i = l}^{r}[S_i =e]xy$ 就是 $l$ ~ $r$ 中 $e$ 的数量乘以定值 $x$ 、 $y$ ，至于 $e$ 的数量也可以用一个前缀和 $E[]$ 来表示（遍历到 $i$ 时左边 $e$ 的数量）。
2. 对于 $\sum_{i = l}^{r}[S_i =e]pre[i] \times suf[i]$ ，我们可以发现竟然和 $\sum_{i = 1} ^ {l - 1}[S_i =e]{pre[i] \times suf[i]}$ 和 $\sum_{i = r 1} ^ {n}{pre[i] \times suf[i]}$ 中的式子一模一样，而我们之前用了一个 $sum[]$ 来维护 $pre[i] \times suf[i]$ ，这个时候 $\sum_{i = l}^{r}[S_i =e]pre[i] \times suf[i]$ = $sum[r] - sum[l - 1]$ 。
3. 这个式子是最难想到的点。化简 $\sum_{i = l}^{r}[S_i =e](x \times suf[i] y \times pre[i])$ ，对于 $S_l = e,S_{l 1} = e,......S_r = e$ ，等式有贡献为
  $x \times suf[l] y \times pre[l] x \times suf[l 1] y \times pre[l 1] ...... x \times suf[r] y \times pre[r] \\ \Leftrightarrow \\ x \times (suf[l] suf[l 1] ...... suf[r]) y \times (pre[l] pre[l 1] ...... pre[r])$
  ==设 $psuf[]$ 为 $suf[]$ 的前缀和、 $ppre[]$ 为 $pre[]$ 的前缀和，也就是 前缀和的前缀和==，其计算同样在预处理函数中进行。那么 $\sum_{i = l}^{r}[S_i =e](x \times suf[i] y \times pre[i])$ = $x \times (psuf[r] - psuf[l - 1]) y \times (ppre[r] - ppre[l - 1])$ ，也可以 $O(1)$ 地算出来。

综上，我们可以得到：

ans = sum[l - 1] (sum[n] - sum[r]) \\ \\ ans = x \times y \times (E[r] - E[l - 1]) - (x \times (psuf[r] - psuf[l - 1]) y \times (ppre[r] - ppre[l - 1])) (sum[r] - sum[l - 1])

最后，在预处理中按顺序处理 $pre[]$ 和 $E[]$ 、 $suf[]$ 、 $sum[]$ 、 $ppre[]$ 和 $psuf[]$ ，最后通过上述的式子 $O(1)$ 地递推出答案即可，总复杂度 $O(n)$ ，算是前缀和中的难题了。

预处理程序：

void init()
{
	for(int i = 1; i <= n; i++)	//pre[]、E[] 
	{
		if(str[i] == 'e') E[i] = E[i - 1] + 1;
		else E[i] = E[i - 1];
		if(str[i] == 'r') pre[i] = pre[i - 1] + 1;
		else pre[i] = pre[i - 1];
	}
	for(int i = n; i >= 1; i--)	//suf[] 
		if(str[i] == 'd') suf[i] = suf[i + 1] + 1;
		else suf[i] = suf[i + 1];
	for(int i = 1; i <= n; i++)	//sum:未翻转时的red的数量 	
		if(str[i] == 'e') sum[i] = sum[i - 1] + pre[i] * suf[i];
		else sum[i] = sum[i - 1];	
	for(int i = 1; i <= n; i++)	//ppre[]、psuf[]
		if(str[i] == 'e')
		{
			ppre[i] = ppre[i - 1] + pre[i];	
			psuf[i] = psuf[i - 1] + suf[i] ;
		}
		else
		{
			ppre[i] = ppre[i - 1];
			psuf[i] = psuf[i - 1];
		}
}

3. AC Code

/*
前缀和 + 前缀和的前缀和
https://ac.nowcoder.com/acm/contest/91592/E
 
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int pre[N];	//前缀r的数量 
int suf[N];	//后缀d的数量
int ppre[N];	//pre的前缀和，只有str[i]=='e'时增加 
int psuf[N];	//suf的前缀和，只有str[i]=='e'时增加
int E[N];	//遍历i时前缀e的数量 
ll sum[N]; 	//未翻转时的red的数量 
int n;
string str;

void init()
{
	for(int i = 1; i <= n; i++)	//pre[]、E[] 
	{
		if(str[i] == 'e') E[i] = E[i - 1] + 1;
		else E[i] = E[i - 1];
		if(str[i] == 'r') pre[i] = pre[i - 1] + 1;
		else pre[i] = pre[i - 1];
	}
	for(int i = n; i >= 1; i--)	//suf[] 
		if(str[i] == 'd') suf[i] = suf[i + 1] + 1;
		else suf[i] = suf[i + 1];
	for(int i = 1; i <= n; i++)	//sum:未翻转时的red的数量 	
		if(str[i] == 'e') sum[i] = sum[i - 1] + pre[i] * suf[i];
		else sum[i] = sum[i - 1];	
	for(int i = 1; i <= n; i++)	//ppre[]、psuf[]
		if(str[i] == 'e')
		{
			ppre[i] = ppre[i - 1] + pre[i];	
			psuf[i] = psuf[i - 1] + suf[i] ;
		}
		else
		{
			ppre[i] = ppre[i - 1];
			psuf[i] = psuf[i - 1];
		}
}
void slove()	//O(1) 
{
	int l,r; cin>>l>>r;
	ll ans1 = sum[l - 1] + (sum[n] - sum[r]);	//1~l-1和r+1~n的e的贡献，即非反转区间的e的贡献 
	ll x = pre[l - 1] + pre[r],y = suf[r + 1] + suf[l];
	ll ans2 = x * y * (E[r] - E[l - 1]) - (x * (psuf[r] - psuf[l - 1]) + y * (ppre[r] - ppre[l - 1])) + (sum[r] - sum[l - 1]);
	ll ans = ans1 + ans2;
	cout<<ans<<endl;
}
int main()
{
	int t = 1; //cin>>t;
	cin>>n>>t;
	cin>>str; str = "*" + str;
	init();
	while(t--)
	{
		slove();
	}
	return 0;
}

牛客周赛 63 E 小红的red计数