I、智乃的密码

首先把这几个条件拆开来看，也就是变成这样6个条件：

1、长度不小于$LL$

2、长度不大于$RR$

3、有小写英文字母

4、有大写英文字母

5、有数字

6、有特殊字符

你发现这6个条件可以拆开分别考虑。

同时这6个条件在固定所选子串的其中一个端点后，另一个端点的合法性是单调的。

所以可以使用二分或者尺取的方式直接判断每一个条件的合法区间。

最后取一个合法区间的并集即可。

时间复杂度$O(N)O(N)$，空间复杂度$O(N)O(N)$

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,l,r,a[4][MAXN],limit[4];
long long ans;
char s[MAXN];
void presum(int a[])
{
	for(int i=1;i<=n;++i)
	{
		a[i]+=a[i-1];
	}
}
bool has(int a[],int l,int r)
{
	return a[r]-a[l-1]>0;
}
int type(char c)
{
	if(c>='A'&&c<='Z')return 0;
	if(c>='a'&&c<='z')return 1;
	if(c>='0'&&c<='9')return 2;
	return 3;
}
int get_limit()
{
	int temp[4];
	memcpy(temp,limit,sizeof(temp));
	sort(temp,temp+4);
	return temp[1];
}
int cal(int border)
{
	int L=1,R=n;
	L=max(border-r+1,L);
	R=min(border-l+1,R);
	R=min(get_limit(),R);
	return L<=R?R-L+1:0;
}
int main()
{
	scanf("%d %d %d",&n,&l,&r);
	scanf("%s",s+1);
	assert(strlen(s+1)==n);
	for(int i=1;i<=n;++i)
	{
		a[type(s[i])][i]++;
	}
	for(int i=0;i<4;++i)
	{
		presum(a[i]);
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<4;++j)
		{
			while(has(a[j],limit[j]+1,i))++limit[j];
		}
		ans+=cal(i);
	}
	printf("%lld\n",ans);
	return 0;
}