这题不是黄吗。

我们显然可以做到 $O(1)$ 计算 $f(R)$。

公式：

$$\begin{aligned} \text{get}(l,r) =\ &C_r A_r^2 - C_r D_r - B_r A_r^2 + B_r D_r - A_r^4 + A_r^2 D_r + (r+1) A_r^3 - (r+1) A_r D_r \\ &+ E_r A_r - G_r + D_r A_r^2 - H_r A_r - (r+1) D_r A_r + (r+1) H_r - F_r A_r + I_r \\ &- C_r A_r A_{l-1} + B_r A_r A_{l-1} + A_r^3 A_{l-1} - (r+1) A_r^2 A_{l-1} - E_r A_{l-1} - D_r A_r A_{l-1} \\ &+ (r+1) D_r A_{l-1} + F_r A_{l-1} \\ &+ C_r D_{l-1} - B_r D_{l-1} - A_r^2 D_{l-1} + (r+1) A_r D_{l-1} + G_{l-1} + H_{l-1} A_r - (r+1) H_{l-1} - I_{l-1} \end{aligned}$$

其中：

$$A_i=\sum_{j=1}^i[s_j=\bm{3}]$$ $$B_i=\sum_{j=1}^ij\cdot[s_j=\bm{3}]$$ $$C_i=\sum_{j=1}^ia_{j-1}\cdot[s_j=\bm{3}]$$ $$D_i=\sum_{j=1}^ia_{j}\cdot[s_j=\bm{3}]$$ $$E_i=\sum_{j=1}^ib_{j}\cdot[s_j=\bm{3}]$$ $$F_i=\sum_{j=1}^ic_j\cdot[s_j=\bm{3}]$$ $$G_i=\sum_{j=1}^ie_j\cdot[s_j=\bm{3}]$$ $$H_i=\sum_{j=1}^id_j\cdot[s_j=\bm{3}]$$ $$I_i=\sum_{j=1}^if_j\cdot[s_j=\bm{3}]$$

剩下的，若 $[l,r]$ 成立，$[l,r+1]$ 成立，双指针。

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int maxn=1e6+10;
#define int __int128
bool b[maxn];
__int128 qzh[maxn],pqzh[maxn],qqzh[maxn],q2qzh[maxn],qpqzh[maxn],qqqzh[maxn],qqpqzh[maxn],qq2qzh[maxn],qqqqzh[maxn];
__int128 tans=0;
//pqzh:[l,r]内3的位置之和
//qqzh:[l,r]内qzh[3的位置-1]之和
//q2qzh:[l,r]内qzh[3的位置]之和
//qpqzh:[l,r]内pqzh[3的位置]之和
//qqqzh:[l,r]内qqzh[3的位置]之和
//qqpqzh:[l,r]内qpqzh[3的位置]之和
//qq2qzh:[l,r]内q2qzh[3的位置]之和
//qqqqzh:[l,r]内qqqzh[3的位置]之和
string s;
__int128 n,k;
__int128 zero=0;
__int128 get(int l,int r){
	__int128 ans=0;
	__int128 maya=qzh[r]-qzh[l-1];
	ans=qqzh[r]*qzh[r]*maya;
	ans=ans+(zero-qqzh[r]*(q2qzh[r]-q2qzh[l-1])-pqzh[r]*qzh[r]*maya+pqzh[r]*(q2qzh[r]-q2qzh[l-1])-qzh[r]*qzh[r]*qzh[r]*maya+qzh[r]*qzh[r]*(q2qzh[r]-q2qzh[l-1])+(r+1)*qzh[r]*qzh[r]*maya
		-(r+1)*qzh[r]*(q2qzh[r]-q2qzh[l-1])+qpqzh[r]*maya-(qqpqzh[r]-qqpqzh[l-1])+q2qzh[r]*qzh[r]*maya-(qq2qzh[r]-qq2qzh[l-1])*qzh[r]-(r+1)*q2qzh[r]*maya+(r+1)*(qq2qzh[r]-qq2qzh[l-1])
		-qqqzh[r]*maya+qqqqzh[r]-qqqqzh[l-1]);
	return ans;
}
/*
*/
bool check(int l,int r){
	return get(l,r)>=k;
}
inline __int128 read()
{
	__int128 x = 0;
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x = x * 10 + c - '0';
		c = getchar_unlocked();
	}
	return x;
}
inline std::string readline()
{
	std::string x = "";
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x += c;
		c = getchar_unlocked();
	}
	return x;
}
void write(__int128 x)
{
	if (x <= 9)
	{
		putchar_unlocked(x + '0');
		return;
	}
	write(x / 10);
	putchar_unlocked(x % 10 + '0');
}
inline void writeline(__int128 x)
{
	write(x);
	putchar_unlocked('\n');
}

signed main(){
	freopen("sorrow.in","r",stdin);
	freopen("sorrow.out","w",stdout);
//	ios;
//	cin.tie(0);
//	cout.tie(0);
	n=read(),k=read();
	s=readline();
	for(int i=0;i<(int)s.size();++i){
		b[i+1]=s[i]=='3';
		qzh[i+1]=qzh[i]+b[i+1];
	}
	for(int i=1;i<=n;++i){
		pqzh[i]=pqzh[i-1]+i*b[i];
		qqzh[i]=qqzh[i-1]+qzh[i-1]*b[i];
		q2qzh[i]=q2qzh[i-1]+qzh[i]*b[i];
		qpqzh[i]=qpqzh[i-1]+pqzh[i]*b[i];
		qqqzh[i]=qqqzh[i-1]+qqzh[i]*b[i];
		qqpqzh[i]=qqpqzh[i-1]+qpqzh[i]*b[i];
		qq2qzh[i]=qq2qzh[i-1]+q2qzh[i]*b[i];
		qqqqzh[i]=qqqqzh[i-1]+qqqzh[i]*b[i];
	}
	int l,r=1;
	for(l=1;l<=n;l++){
		for(;!check(l,r)&&r<=n;r++);
		tans+=n-r+1;
	}
	write(tans);
}

注意到子串的权值在其中一个端点固定时随着另一个端点向外扩展而单调递增，可以使用双指针统计答案。

将原序列反转，改为匹配子序列 $\{\texttt 2, \texttt 3, \texttt 3, \texttt 3\}$，分别维护子序列 $\{\texttt 2\}, \{\texttt 2, \texttt 3\}, \{\texttt 2, \texttt 3, \texttt 3\}, \{\texttt 2, \texttt 3, \texttt 3, \texttt 3\}$ 的出现次数即可实现双指针移动时对权值的实时计算。

最终的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，其中输入的字符串 $S$ 不计入空间复杂度。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 12;
inline __int128 read()
{
	__int128 x = 0;
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x = x * 10 + c - '0';
		c = getchar_unlocked();
	}
	return x;
}
inline std::string readline()
{
	std::string x = "";
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x += c;
		c = getchar_unlocked();
	}
	return x;
}
void write(__int128 x)
{
	if (x <= 9)
	{
		putchar_unlocked(x + '0');
		return;
	}
	write(x / 10);
	putchar_unlocked(x % 10 + '0');
}
inline void writeline(__int128 x)
{
	write(x);
	putchar_unlocked('\n');
}
int main()
{
	freopen("sorrow.in", "r", stdin);
	freopen("sorrow.out", "w", stdout);
	__int128 n = read(), k = read();
	string s = readline();
	reverse(s.begin(), s.end());
	s = ' ' + s;
	__int128 r = 0, ans = n * (n + 1) / 2;
	__int128 c3 = 0, c2 = 0, c23 = 0, c233 = 0, c2333 = 0;
	for (int i = 1; i <= n; i++)
	{
		while (c2333 < k && r <= n)
		{
			r++;
			if (s[r] == '2') c2++;
			if (s[r] == '3')
			{
				c3++;
				c2333 += c233;
				c233 += c23;
				c23 += c2;
			}
		}
		ans -= (r - i);
		if (s[i] == '3') c3--;
		if (s[i] == '2')
		{
			c2--;
			c2333 -= c3 * (c3 - 1) * (c3 - 2) / 6;
			c233 -= c3 * (c3 - 1) / 2;
			c23 -= c3;
		}
	}
	writeline(ans);
	return 0;
}