题意跟某道我出的等差子序列求最值非常像……
反正询问的长度只有10种，你就建立10批树状数组，每组的公差是确定的，首项不同。
然后询问的时候只需要枚举询问串的每一位，找找这一位对应哪棵树状数组即可。
修改的时候会在10棵树状数组里修改，也是算算修改的位置对应哪一棵即可。
要注意，一共有4种字符，每个树状数组其实分成4个，就只需要单点修改，维护前缀和了……
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,ma[201];
char a[100010];
struct BIT{
int siz;
int* d;
void init(int siz){
this->siz=siz;
d=new int[siz];
memset(d,0,sizeof(int)*siz);
}
void Update(int p,int v){for(;p<siz;p+=(p&(-p))) d[p]+=v;}
int Query(int p){int res=0; for(;p;p-=(p&(-p))) res+=d[p]; return res;}
}T[11][11][4];
int main(){
ma['A']=0;
ma['T']=1;
ma['G']=2;
ma['C']=3;
scanf("%s%d",a+1,&m);
n=strlen(a+1);
for(int i=1;i<=10;++i){
for(int j=1;j<=i;++j){
for(int k=0;k<4;++k){
T[i][j][k].init(n/i+5);
}
for(int k=j,l=1;k<=n;k+=i,++l){
T[i][j][ma[a[k]]].Update(l,1);
}
}
}
int op,x,y,z;
char e[14];
for(;m;--m){
scanf("%d%d",&op,&x);
if(op==1){
scanf("%s",e);
for(int i=1;i<=10;++i){
int x1=x/i+(x%i!=0);
int x0=x-(x1-1)*i;
T[i][x0][ma[a[x]]].Update(x1,-1);
T[i][x0][ma[e[0]]].Update(x1,1);
}
a[x]=e[0];
}
else{
int ans=0;
scanf("%d%s",&y,e+1);
int len=strlen(e+1);
for(int i=1;i<=len;++i){
int X=x+i-1;
int X1=X/len+(X%len!=0);
int X0=X-(X1-1)*len;
// int tmp=X1 + (y-x+1)/len + ((y-x+1)%len>=i) - 1;
ans+=(T[len][X0][ma[e[i]]].Query(X1 + (y-x+1)/len + ((y-x+1)%len>=i) - 1) -
T[len][X0][ma[e[i]]].Query(X1-1));
}
printf("%d
",ans);
}
}
return 0;
}