跟上场相不同的地方，上场我们只需要讨论k和y即可，本题我们需要对ckl三个字母均进行讨论。我们可以把k看作上题的y。只要求出每个k的贡献即可。

每个k给的贡献即k前面 $Cnt_c$ $\times$ $Cnt_l$ 。

然后就是数据范围的变化，如果仅仅只是暴力寻找 $l$ ~ $r$ 中的每个k，也会超时。于是我们需要运用点巧妙的数学运算：

$$\sum_{i=1}^r[S_i = k]((cnt_c[l-1]+(cnt_c[r]-cnt_c[i])) \times (cnt_l[r+1]+(cnt_l[l] - cnt_l[i]))) $$

化简为：

$$\sum_{i=l}^r[S_i=k]((cnt_c[l-1]+cnt_c[r]-cnt_c[i]) \times (cnt_l[r+1]+cnt_l[l]-cnt_l[i])) $$

我们可以让$x=cnt_c[l-1]+cnt_c[r]$ , $y=cnt_l[r+1]+cnt_l[l]$ ;

于是又可以拆分为三部分：

$$\sum_{i=l}^r[S_i=k]xy - \sum_{i=l}^r[S_i=k](x \times cnt_l[i] + y \times cnt_c[i]) \times \sum_{i=l}^r[S_i=k](cnt_c[i]\times cnt_l[i]) $$

我们分别讨论三部分内容：

1. $\sum_{i=l}^r[S_i=k]xy$ 就是 $l$ ~ $r$ 中 $k$ 的数量乘以定值$x,y$ ；在这里我们可以再用一个前缀和 $E[]$ 储存 $k$ 的值，方便查询；

2. $\sum_{i=l}^r[S_i=k](x \times cnt_l[i] \times y \times cnt_c[i])$ 我们发现居然是每个 $k$ 在字符串未翻转前的贡献，我们又可以用一个前缀和数组 $Sum[]$ 来维护；

3. 第三个式子最难处理，我们需要把其再次拆分为

   $$x\times cnt_l[l] + y \times cnt_c[l] + x\times cnt_l[l+1] + y \times cnt_c[l+1] +\dots+x\times cnt_l[r] + y \times cnt_c[r] $$

也就是

$$x \times \sum_{i=l}^rcnt_l[i] + y \times \sum_{i=l}^rcnt_c[i] $$

然后我们发现：

$$\sum_{i=l}^rcnt_l[i] 和 \sum_{i=l}^rcnt_c[i] $$

不就又是两个前缀和？

经过这么一大串不太简便的数学推演之后，我们可以很简单的求出我们需要的答案

$$ans=x\times y \times (E[r]-E[l-1]) - (x\times (scnt_l[r]-scnt_l[l-1])+y\times (scnt_l[r]-scnt_l[l-1]))+(sum[r]-sum[l-1]) $$

然后就可以$O(1)$ 的时间复杂度求出答案咯~

数学，如此简单？

附上$AC$ $Code$ 👍

前缀和 + 前缀和的前缀和 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = 1e5 + 5;
int pre[N];	//前缀c的数量 
int suf[N];	//后缀l的数量
int ppre[N];	//pre的前缀和，只有str[i]=='k'时增加 
int psuf[N];	//suf的前缀和，只有str[i]=='k'时增加
int E[N];	//遍历i时前缀k的数量 
ll sum[N]; 	//未翻转时的ckl的数量 
int n;
string str;

void init()
{
	for(int i = 1; i <= n; i++)	//pre[]、E[] 
	{
		if(str[i] == 'k') E[i] = E[i - 1] + 1;
		else E[i] = E[i - 1];
		if(str[i] == 'c') pre[i] = pre[i - 1] + 1;
		else pre[i] = pre[i - 1];
	}
	for(int i = n; i >= 1; i--)	//suf[] 
		if(str[i] == 'l') suf[i] = suf[i + 1] + 1;
		else suf[i] = suf[i + 1];
	for(int i = 1; i <= n; i++)	//sum:未翻转时的ckl的数量 	
		if(str[i] == 'k') 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] == 'k')
		{
			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];
		}
}

int slove()	//O(1) 查询
{
	int l,r; cin>>l>>r;
	ll ans1 = sum[l - 1] + (sum[n] - sum[r]);	//1~l-1和r+1~n的k的贡献，即非反转区间的k的贡献 
	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;
}
signed main()
{
	int t = 1; //cin>>t;
	cin>>n>>t;
	cin>>str; str = "*" + str;
	init();
	while(t--)
	{
		slove();
	}
return 0;
}

请先完成第三场招新赛题目：TLE之后我想回到过去……