博客

题意：给出一个长串s（length<=1e5），字符集={A，T，G，C}，现在给出q（<=1e5）次询问，询问分成两种：

一：给定l，r，matchString（字符集={A，T，G，C}，且length<=10），要求先将matchString循环足够多次（使得长度大于r-l），然后把这个循环串和原串s的[l,r]区间进行匹配，输出有几个位置匹配成功。

二：给定index和c，要求把原串s的index位置的字符变成c

题解：首先，先看看如何匹配，记matchString的长度是len，考虑他的matchString[0]这个字符，他将循环出现在l,l+len,l+len*2,l+len*3……这些位置和s串相应字符尝试匹配。因此len其实是一个进制，matchString[0]的匹配数量等于：l-r中所有同余位置的匹配量，那么就等价于一个区间查询、单点修改问题了。

而且注意到len<=10，总共只有1-10这么10种进制，因此查询询问可以分成10种。而对于一个进制x，经过上边的分析，我们知道它相当于0-x这样x种区间查询。而我们又要对于字符集的四个字符都分开维护，因此总共需要维护10*（1+10）/2*4=220棵树状数组（BIT）。我的代码用面向对象的思想，把BIT的操作封装起来。这样好读也好写。讲的并不是很清楚，看代码会简单一些。

Code：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
int lowbit(int x){
    return (x&-x);
}
struct BIT{
    int tree[MAXN];
    void add (int start,int delta){
        while (start<MAXN){
            tree[start]+=delta;
            start+=lowbit(start);
        }
    }
    int get (int start){
        int ans =0;
        while (start>0){
            ans+=tree[start];
            start-=lowbit(start);
        }
        return ans;
    }
}tree[11][11][4];
int q;
int mp[256];
char a[MAXN];
char tempString [20];
int main(){
    mp['A']=0;
    mp['T']=1;
    mp['G']=2;
    mp['C']=3;
    scanf("%s%d",a+1,&q);
    int length = strlen(a+1);
    for (int i=1;i<=10;i++){
        for (int j=1;j<=length;j++){
            tree[i][j%i][mp[a[j]]].add(j,1);
        }
    }
    while (q--){
        int op;
        scanf("%d",&op);
        if (op==1){
            int start;
            scanf("%d%s",&start,tempString);
            for (int i=1;i<=10;i++){
                tree[i][start%i][mp[a[start]]].add(start,-1);
                tree[i][start%i][mp[tempString[0]]].add(start,1);
            }
            a[start]=tempString[0];
        }else{
            int l,r;
            scanf("%d%d%s",&l,&r,tempString);
            int len = strlen(tempString);
            int ansSum = 0;
            for (int i=0;i<len;i++){
                ansSum+=tree[len][(l+i)%len][mp[tempString[i]]].get(r)-tree[len][(l+i)%len][mp[tempString[i]]].get(l-1);
            }
            cout<<ansSum<<endl;
        }
    } 
    return 0;
}