CodeForces 828E DNA Evolution（树状数组）题解

时间：2022-09-10 11:05:28

题意：给你一个串k，进行两个操作：

“1 a b”：把a位置的字母换成b

“2 l r s”：求l到r有多少个字母和s匹配，匹配的条件是这样：从l开始无限循环s形成一个串ss，然后匹配ss和指定区间的匹配个数，如图。

CodeForces 828E DNA Evolution（树状数组）题解

思路：用树状数组预处理。因为模板串是不断重复循环的，所以我们可以一个位置一个位置求。对于长len的模板串来说，如果位置i，j满足 i%len == j%len，那么i和j匹配时对模板串来说是一样的（匹配同一个字符）。所以我们定义node[字母][模板串长度][相对位置][位置]来遍历某个位置字符在所有可能的相对位置的情况。

参考：Codeforces - 828E DNA Evolution —— 很多棵树状数组

代码：

#include<stack>

#include<vector>

#include<queue>

#include<set>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#define ll long long

#define ull unsigned long long

using namespace std;

const int maxn =  + ;

const int seed = ;

const int MOD = ;

const int INF = 0x3f3f3f3f;

char s[maxn];

int h[];

int node[][][][maxn];

int lowbit(int x){

    return x&(-x);

}

void update(int letter, int x, int val){

    for(int i = x; i < maxn; i += lowbit(i)){

        for(int len = ; len <= ; len++){

            node[letter][len][x % len][i] += val;

        }

    }

}

int sum(int letter, int x, int len, int pos){

    int ans = ;

    for(int i = x; i > ; i -= lowbit(i)){

        ans += node[letter][len][pos][i];

    }

    return ans;

}

int query(int l, int r, int len, int letter, int pos){

    return sum(letter, r, len, pos) - sum(letter, l - , len, pos);

}

int main(){

    memset(node,  , sizeof(node));

    h['A'] = , h['G'] = , h['C'] = , h['T'] = ;

    scanf("%s", s + );

    int len = strlen(s + );

    for(int i = ; i <= len; i++){

        update(h[s[i]], i, );

    }

    int q;

    scanf("%d", &q);

    while(q--){

        int o,u,v;

        char ss[];

        scanf("%d", &o);

        if(o == ){

            scanf("%d%s", &u, ss);

            update(h[s[u]], u, -);

            update(h[ss[]], u, );

            s[u] = ss[];

        }

        else{

            scanf("%d%d%s", &u, &v, ss);

            len = strlen(ss);

            int ans = ;

            for(int i = ; i < len; i++){

                ans += query(u, v, len, h[ss[i]], (u + i) % len);

            }

            printf("%d\n", ans);

        }

    }

    return ;

}

/*

ATGCATGC

4

2 1 8 ATGC

2 2 6 TTT

1 4 T

2 2 6 TA

*/

相关文章