文章目录
题目链接:
http://codeforces.com/problemset/problem/828/E
题意:先给一个DNA序列,然后有两种操作
操作1:把 x 位置的碱基改成 c
操作2:给一个 L 和一个 R ,以及一个字符串 s ,这个字符串s是一直循环重复的,比如s=‘ATC’,那就是’ATCATCATCATC…'一直循环下去。问在[L,R]中,对应位置字符相同的有多少个?
看了题解之后,我才反应过来,DNA序列与所给的这个字符串是从头开始对齐然后来比对的,而不需要找对应位置相同最多而去移动他,因此所有信息已给出,两个串的相对位置就是固定的了,而这道题的关键就是所给的字符串 s 的长度非常小,不然就不好做了
哇~所以才有的长这种样子的树状数组,<mark>就是DNA中第 i 个的这种字符,与长度为 s 的字符串延长后的第 i 个这种字符相同的数量</mark>,因为4种碱基都要统计,所以要4个树状数组来统计
每种碱基的树状数组来统计当把DNA分成len段len段的时候的这种碱基在x%len位置上的个数
这道题是个让我阔以回味的题~good题
#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
char DNA[maxn];
struct BitTree
{
int tree[maxn];
void add(int pos,int v)
{
for(int i=pos; i<maxn; i+=i&-i)tree[i]+=v;
}
int getsum(int pos)
{
int res=0;
for(int i=pos; i>=1; i-=i&-i)res+=tree[i];
return res;
}
int query(int L,int R)
{
return getsum(R)-getsum(L-1);
}
};
BitTree a[11][11][4];
int main()
{
map<char,int>Mp;
Mp['A']=0;
Mp['G']=1;
Mp['C']=2;
Mp['T']=3;
while(cin>>(DNA+1))
{
memset(a,0,sizeof a);
int N=strlen(DNA+1);
/*预处理出所有信息存到树状数组中*/
//把DNA分成len段len段的,存储对应位置是某个碱基的个数
for(int len=1; len<=10; len++)
{
for(int i=1; i<=N; i++)
{
a[len][i%len][Mp[DNA[i]]].add(i,1);
}
}
int Q;
cin>>Q;
while(Q--)
{
int cmd;
scanf("%d",&cmd);
char s[15];
if(cmd==1)
{
int x;
scanf("%d%s",&x,s);
for(int len=1; len<=10; len++)
{
a[len][x%len][Mp[DNA[x]]].add(x,-1);//手贱x写成i了,以后都改成while(Q--)好了,不用for循环了
a[len][x%len][Mp[s[0]]].add(x,1);
}
DNA[x]=s[0];//这个忘了改了就WA了
}
else
{
int L,R;
scanf("%d%d%s",&L,&R,s);
int len=strlen(s);
int res=0;
for(int i=0;i<len;i++)
{
res+=a[len][(i+L)%len][Mp[s[i]]].query(L,R);//根据预处理出来的信息来查询有多少个
}
cout<<res<<endl;
}
}
}
}