Codeforces 827C

827C - DNA Evolution

思路：

写4*10*10个树状数组，一个维度是4（ATCG），另一个维度是长度len，另一个维度是pos%len，因为两个pos,如果len和pos%len相同，那么它们就在一个树状数组里。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))

const int N=1e5+5;
int a[4][11][10][N];
int n;
int lowbit(int x)
{
    return x&(-x); 
} 
void update(int x,int pos,int c,int d)
{
    while(x<=n)
    {
        for(int i=1;i<=10;i++)
        a[c][i][pos%i][x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x,int pos,int c,int len)
{
    int ans=0;
    while(x>0)
    {
        ans+=a[c][len][pos%len][x];
        x-=lowbit(x);
    }
    return ans;
}
int mp[200];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s,t;
    int m,a,l,r;
    mp['A']=0;
    mp['T']=1;
    mp['C']=2;
    mp['G']=3;
    cin>>s;
    n=s.size();
    for(int i=0;i<s.size();i++)
    {
        update(i+1,i+1,mp[s[i]],1);
    }
    cin>>m;
    while(m--)
    {
        cin>>a;
        //cout<<1<<endl;
        if(a==2)
        {
            cin>>l>>r>>t;
            int ans=0;
            for(int i=0;i<t.size();i++)
            ans+=sum(r,i+l,mp[t[i]],t.size())-sum(l-1,i+l,mp[t[i]],t.size());
            cout<<ans<<endl;
        }
        else
        {
            cin>>l;
            cin>>t;
            update(l,l,mp[s[l-1]],-1);
            update(l,l,mp[t[0]],1);
            s[l-1]=t[0];    
        }
    }
    return 0; 
}