自动搬运

查看原文

来自洛谷，原作者为

	LinkCatTree 欢迎【蓝金勾】大佬壶关喵

搬运于2025-08-24 23:00:54，当前版本为作者最后更新于2025-01-01 09:59:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑如果字符串 $s$ 和 $t$ 是相近的，两个字符串会满足什么特征。由于每次会对相邻两个字符进行操作，这两个字符的下标必为一奇一偶，因此字符串奇偶两位上字符之和的差也不会变（字符之和：我们把 $\text{a}$ 看做 $0$，把 $\text{b}$ 看作 $1$……以此得到的所有数字的总和）。因此我们的出：$s$ 奇偶位上字符之和之差与 $t$ 奇偶位上字符之和之差相同。我们可以 $\mathcal{O}(n)$ 计算一开始的差，然后对于每个询问 $\mathcal{O}(1)$ 维护，总时间复杂度 $\mathcal{O}(n+q)$。

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n,q,sum1,sum2;
char s[N],t[N];

int main() {
	freopen("tmp.in","r",stdin);
	scanf("%d%d%s%s",&n,&q,s+1,t+1);
	for(int i=1;i<=n;i++)
		if(i&1) sum1+=s[i]-'a';
		else sum1-=s[i]-'a';
	((sum1%=26)+=26)%=26;
	for(int i=1;i<=n;i++)
		if(i&1) sum2+=t[i]-'a';
		else sum2-=t[i]-'a';
	((sum2%=26)+=26)%=26;
	if(sum1!=sum2) printf("ne\n");
	else printf("da\n");
	while(q--) {
		int p; char op[3];
		scanf("%d%s",&p,op+1);
		if(p&1) sum1+=op[1]-s[p];
		else sum1-=op[1]-s[p];
		s[p]=op[1],((sum1%=26)+=26)%=26;
		if(sum1!=sum2) printf("ne\n");
		else printf("da\n");
	}
	return 0;
}