Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution(多颗树状数组+思维)
程序员文章站
2022-07-12 12:30:47
...
题目链接
题意:给出一个DNA序列(n<=1e5),有两种操作:
-
1 x c 表示将x位置的碱基换成c
-
2 l r e 表示一个询问:e字符串(|e|<=10)在[l,r]区间内循环出现,问有多少个位置的字符相同?
思路:由于要查询的字符串长度很小,我们可以预处理以下,c【x】【y】【z】【i】代表的是对于长度为y的e字符串,第i个字母在e中的对应位置是x,第i个字符串为z的个数。(你可以这么想初始字符串的每个位置i在每个长度的e字符串中的位置都是固定可以算出来的,也就是i%j)。
#include <bits/stdc++.h>
using namespace std;
#define lowbit(i) (i)&(-i)
typedef long long ll;
const int maxn=1e5+5;
char s[maxn],str[12];
ll c[11][11][4][maxn];
void update(int x,int y,int z,int pos,int v)//x指对应位置,y是长度,z是pos这个位对应的字符,pos是当前位
{
while(pos<maxn) c[x][y][z][pos]+=v,pos+=lowbit(pos);
}
int query(int x,int y,int z,int pos)
{
int res=0;
while(pos>0) res+=c[x][y][z][pos],pos-=lowbit(pos);
return res;
}
int turn(char x)
{
if(x=='A') return 1;
else if(x=='T') return 2;
else if(x=='G') return 3;
else return 4;
}
int main()
{
char x;
scanf("%s",s+1);
int len=strlen(s+1),op,l,r,q;
for(int i=1;i<=len;++i)
for(int j=1;j<=10;++j)
update(i%j,j,turn(s[i]),i,1);
scanf("%d",&q);
while(q--)
{
scanf("%d",&op);
if(op==1)
{
cin>>l>>x;
for(int i=1;i<=10;++i)
update(l%i,i,turn(x),l,1),update(l%i,i,turn(s[l]),l,-1);
s[l]=x;
}
else{
cin>>l>>r>>str;
int size=strlen(str),ans=0;
for(int i=1;i<=size;++i)
ans+=query((l+i-1)%size,size,turn(str[i-1]),r)-query((l+i-1)%size,size,turn(str[i-1]),l-1);
printf("%d\n",ans);
}
}
}