CF827C 题解

· · 题解

题目大意：

给一个长度只包含 A,T,C,G 的字符串，q 次操作，每次有两种：

  1. 修改某个位置的字母。
  2. 给定一个字符串 s(|s|\le 10)，生成一个重复的新串 sssss \cdots。询问 [L,R] 中有几个字母跟新字符串对应。

Sol

设母串为 T，询问字符串为 s。

注意到每次询问中的字符串 s 长度不超过 10，记 len = |s|。

假设每次询问的区间都是 [1,n]。

我们只对 T 中前 len 个字符考虑。

对于 s_i，我们要判断的是 T_i，T_{i+len}，T_{i+2len} \cdots T_{i+klen} (i+klen\le n) 是否等于 s_i 即可。

分析对于每种可能的 len (最多 10 种情况）

  1. 对于每个 i。
  2. 对于每个可能的 s_i。

我们都建立一个长度为 n 的树状数组，其中第 j 位表示 T_j 是否和 s_i 相等。

且其中 j 只需要取 \{i,i+len,i+2len,\cdots,i+klen\}。

总共需预处理 4 \times (1+2+3+\cdots+10)=220 个长度为 n 的树状数组。

再分析对于一般询问 [L,R]，长度为 len 的 s

只需要对 T_{L,\cdots,R} 的前 len 个字符考虑即可。

对于 T_L，我们先找到 i。

然后在 (len,i,s_i) 对应的树状数组上查询 [L,R] 上有几个 1 即可。

核心代码

#define N 100010
int n,m, sum[4][11][11][N],has[128];
char t[N],s[20];
int lowbit(int x){
    return x&(-x);
}
void change(int c,int p,int v){
    for(int x=p;x<=n;x+=lowbit(x)){
        for(int j=1;j<=10;j++){
            sum[c][j][p%j][x]+=v;
        }
    }
}
int query(int c,int len,int p,int x){
    int ret=0;
    while(x){
        ret+=sum[c][1en][p][x];
        x-=lowbit(x);
    }
    return ret;
}
int main() {
    has['A']=0,has['T']=1,has['C']=2,has['G']=3;
    scanf("%s" ,t+1);
    n=strlen(t+1); 
    for(int i=1;i<=n;i++)
        change(has[t[i]],i,1);
    int op,1,r,x;
    char c;
    m=read();
    while(m--){
        op=read();
        if(op==1){
            scanf("%d %c",&x,&c); 
            change(has[t[x]],x,-1);
            change(has[c],x,1);
            t[x]=c;
        }else{
            scanf("%d %d %s",&1,&r,&s);
            int len=strlen(s), ans=0;
            for(int i=0;i<len;i++){
                ans+=query(has[s[i]],len, (i+1)%len,r);
                query(has[s[i]],len,(i+l)%len,1-1);
                printf( "%d\n",ans);
            }
        }
    }
    return 0;
}