对c1求前缀和 a[i]表示从第一个字符到第i个字符,一共有几个c1
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
char a[N];
vector<int> r;
int s[N];
int n;
int main(){
cin>>n;
scanf("%s",a+1);
int len=strlen(a+1);
char p,q;
cin>>p>>q;
for(int i=1;i<=len;i++){
if(a[i]==q)r.push_back(i);
if(a[i]==p){
s[i]=s[i-1]+1;
}
if(a[i]!=p) s[i]=s[i-1];
}
// for(int i=0;i<len;i++)cout<<s[i]<<endl;
long long res=0;
for(auto x:r){
if(x-n+1>=0){
res+=s[x-n+1];
}
}
cout<<res<<endl;
return 0;
}
对c2求前缀和 b[i]表示从第最后一个字符到第i个字符(从后往前看),一共有几个c2
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
// typedef pair<int,int> PII;
typedef long long LL;
char str[N];
char c1,c2;
int n;
int b[N];
vector<int> a;
int main(){
cin>>n>>(str+1);
cin>>c1>>c2;
LL len = strlen(str+1);
for(int i=len;i>=1;i--){
if(str[i]==c2)b[i]=b[i+1]+1;
else b[i]=b[i+1];
if(str[i]==c1)a.push_back(i);
}
LL res=0;
while(a.size()){
int i = a.back();
int j = a.back()+n-1;
if(j<=len)
res += b[j];
a.pop_back();
}
cout<<res<<endl;
return 0;
}