本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-13 19:21:58

建议难度评为 $\color{orange}橙$ 或 $\color{yellow}黄$。

题意

给定两长度为 $n$ 的字符串 $s,t$，判断它们是否相近（指可以通过若干次操作使得 $s,t$ 相等），并给定 $Q$ 次修改，每次修改 $s$ 的一个字符，然后再判断是否相近。

对于每次操作，选择一个字符串 $s$ 和位置 $p$，将 $s_p$ 和 $s_{p+1}$ 在字母表上前移一位。

思路

可以发现，将所有操作集中到一个字符串可以使 $s,t$ 相等时，那么 $s,t$ 相近。
注意到，对于 $s_1$，通过操作使其变成 $t_1$ 的操作次数为 $t_1-s_1$，次数对 $26$ 取模。令这个次数为 $a_1$，那么 $s_2$ 便已经进行了 $a_1$ 次操作，需再进行 $t_2-s_2-a_1$ 次操作。以此类推，可求出 $a_n$。
第 $n$ 位是字符串的最后一位，它不可能进行操作，所以当且仅当 $a_n=0$ 时，两字符串相近。对于每次修改，可根据其与 $n$ 的位置差直接修改 $a_n$，进行 $O(1)$ 判断是否相近。

时间复杂度 $O(n+Q)$。

代码

#include<bits\/stdc++.h>
#define int long long
#define F(i,l,r) for(register int i=(l); i<=(r); ++i)
using namespace std;
const int N= 1e6 +50;

int n,Q;
int a[N];
string s,t;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>Q>>s>>t;
	F(i,1,n){
		a[i]=(t[i-1]+26-s[i-1])%26;
		a[i]-=a[i-1];
		if(a[i]<0) a[i]+=26;
	}
	a[n]%=26;
	cout<<(a[n]?"ne\n":"da\n");
	F(i,1,Q){
		int p;char c; cin>>p>>c;
		int t=c-s[p-1];
		s[p-1]=c;
		a[n]+=t*((n-p)&1?1:-1);
		a[n]%=26;
		cout<<(a[n]?"ne\n":"da\n");
	}
	
	return 0;
}