一、题目
点此看题
二、解法
观察到 很小，且字母种类为 ，有一种很神奇的做法，维护 表示考虑字符 ， 长度为 的时候，当前下标模 余 的树状数组，维护还是比较好做的。算答案的时候因为是循环，所以可以把模出来一样的放一起算，直接带值到树状数组里去算即可。
#include <cstdio>
#include <cstring>
const int M = 100005;
int read()
{int x=0,f=1;char c;while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
int n,m,ha[200],b[4][11][10][M];char s[M],c[M];
int lowbit(int x)
{return x&(-x);
}
void insert(int x,int pos,int ty,int f)
{for(;x<=n;x+=lowbit(x))for(int k=1;k<=10;k++)b[ty][k][pos%k][x]+=f;
}
int ask(int x,int pos,int ty,int len)
{int res=0;for(;x>=1;x-=lowbit(x))res+=b[ty][len][pos][x];return res;
}
int query(int x,int y,int pos,int ty,int len)
{return ask(y,pos,ty,len)-ask(x-1,pos,ty,len);
}
int main()
{ha['A']=0;ha['T']=1;ha['G']=2;ha['C']=3;scanf("%s",s+1);n=strlen(s+1);m=read();for(int i=1;i<=n;i++)insert(i,i,ha[s[i]],1);for(int i=1;i<=m;i++){int op=read();if(op==1){int x=read();scanf("%s",c);insert(x,x,ha[s[x]],-1);insert(x,x,ha[c[0]],1);s[x]=c[0];}else{int l=read(),r=read(),ans=0;scanf("%s",c);int len=strlen(c);for(int i=0;i<len;i++)ans+=query(l,r,(l+i)%len,ha[c[i]],len);printf("%d\n",ans);}}
}