欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution(多颗树状数组+思维)

程序员文章站 2022-07-12 12:30:47
...

题目链接
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution(多颗树状数组+思维)
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution(多颗树状数组+思维)
题意:给出一个DNA序列(n<=1e5),有两种操作:

  1. 1 x c 表示将x位置的碱基换成c

  2. 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);
		 }
	 } 
 } 
相关标签: 树状数组