CodeForces 827C Round#423 Div2E&Div1C Solution:树状数组或其他

  • Post author:
  • Post category:其他


题意:给出一个长串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;
}



版权声明:本文为calabash_boy原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。