题目链接：http://codeforces.com/contest/828/problem/E
题解：就是开4个数组举一个例子。
A[mod][res][i]表示到i位置膜mod余数是res的‘A’有多少个。然后以此类推其他碱基。就是单点更新区间求和用树状数组就行具体看一下代码。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = 1e5 + ;
char s[M];
int T[][][][M];
inline void add(int id , int mod , int res , int k , int v) {
++k;
while(k < M) {
T[id][mod][res][k] += v;
k += (k & (-k));
}
}
inline int getsum(int id , int mod , int res , int k) {
int ret = ;
++k;
while(k) {
ret += T[id][mod][res][k];
k -= (k & (-k));
}
return ret;
}
int main() {
scanf("%s" ,s);
int q , n , x , l , r;
char c[];
scanf("%d" , &q);
memset(T , , sizeof(T));
int L = strlen(s);
for(int i = ; i < L ; i++) {
for(int j = ; j <= ; j++) {
if(s[i] == 'A') add( , j , i % j , i , );
if(s[i] == 'T') add( , j , i % j , i , );
if(s[i] == 'G') add( , j , i % j , i , );
if(s[i] == 'C') add( , j , i % j , i , );
}
}
while(q--) {
scanf("%d" , &n);
if(n == ) {
scanf("%d %s" , &x , c);
x--;
for(int i = ; i <= ; i++) {
if(s[x] == 'A') add( , i , x % i , x , -);
if(s[x] == 'T') add( , i , x % i , x , -);
if(s[x] == 'G') add( , i , x % i , x , -);
if(s[x] == 'C') add( , i , x % i , x , -);
}
for(int i = ; i <= ; i++) {
if(c[] == 'A') add( , i , x % i , x , );
if(c[] == 'T') add( , i , x % i , x , );
if(c[] == 'G') add( , i , x % i , x , );
if(c[] == 'C') add( , i , x % i , x , );
}
s[x] = c[];
}
else {
scanf("%d%d%s" , &l , &r , c);
l--, r--;
int len = strlen(c);
int ans = ;
for(int i = ; i < len ; i++) {
if(c[i] == 'A') ans += (getsum( , len , (i + l) % len , r) - (l == ? : getsum( , len , (i + l) % len , l - )));
if(c[i] == 'T') ans += (getsum( , len , (i + l) % len , r) - (l == ? : getsum( , len , (i + l) % len , l - )));
if(c[i] == 'G') ans += (getsum( , len , (i + l) % len , r) - (l == ? : getsum( , len , (i + l) % len , l - )));
if(c[i] == 'C') ans += (getsum( , len , (i + l) % len , r) - (l == ? : getsum( , len , (i + l) % len , l - )));
}
printf("%d\n" , ans);
}
}
return ;
}