B3683.md

[语言月赛202211] String Problem

题目描述

扶苏给你了两个长度为 $n$ 的字符串 $s$ 和 $t$，请你判定这两个字符串是否相同。

扶苏觉得这个问题太简单了，所以她还给出了 $q$ 次操作，每次操作是修改其中一个字符串的某个位置的字符。每次操作过后，都请你回答一次 $s$ 和 $t$ 是否相同。

字符串下标从 1 开始编号。例如，若字符串 $s$ 为 $\texttt {abc}$，要将它的第二个位置修改为 $d$，则修改后的字符串为 $\texttt{adc}$。

输入格式

本题单测试点内有多组测试数据。

输入的第一行是一个整数 $T$，表示数据组数。接下来按顺序给出每组数据的输入：

对每组数据，第一行是两个整数，依次表示字符串长度 $n$ 和操作的次数 $q$。
第二行是一个长度为 $n$ 的字符串，表示 $s$。
第三行是一个长度为 $n$ 的字符串，表示 $t$。
接下来 $q$ 行，每行两个整数 $o, p$ 和一个字符 $c$，其中 $o$ 是 $0$ 或 $1$。

• 若 $o = 0$，则表示将字符串 $s$ 的第 $p$ 个字符修改成 $c$。
• 若 $o = 1$，则表示将字符串 $t$ 的第 $p$ 个字符修改成 $c$。

输出格式

对每组数据，依次输出答案。

每组数据共需要输出 $q + 1$ 行。
首先对初始给定的字符串 $s$ 和 $t$，若他们相同，则输出一行 Yes，否则输出一行 No。
接下来，对每次操作，若操作后两字符串相同，输出一行 Yes，否则输出一行 No。

样例 #1

样例输入 #1

2
3 2
abc
abc
1 2 d
0 2 d
5 0
abdce
acdce

样例输出 #1

Yes
No
Yes
No

提示

样例 1 解释

对第一组数据：

• 输入的字符串 $s = t$，故第一行输出为 Yes。
• 第一次操作，将 $t$ 的第 2 位改为 $\texttt d$，此时 $s = \texttt{abc}$，$t = \texttt{adc}$，$s \neq t$，故第二行输出为 No。
• 第二次操作，将 $s$ 的第 2 位改为 $\texttt d$，此时 $s = \texttt{adc}$，$t = \texttt{adc}$，$s = t$，故第三行输出为 Yes。

对第二组数据：

• 输入的字符串 $s \neq t$，故第四行输出为 No。

数据规模与约定

本题共 10 个测试点，各测试点的规模见下表

测试点编号	$n = $	$q =$
1	$1$	$0$
2	$1000$	$0$
3	$1000$	$0$
4	$1000$	$1000$
5	$1000$	$1000$
6	$1000$	$1000$
7	$10^6$	$10^6$
8	$10^6$	$10^6$
9	$10^6$	$10^6$
10	$10^6$	$10^6$

对全部的测试点，保证 $T = 5$，$s,t$ 均只含小写英文字母，输入的换行符不含 \r，$o \in {0, 1}$，$1 \leq p \leq n$，$c$ 为小写英文字母。

提示

请注意大量的数据读入输出对程序效率造成的影响。

By 一扶苏一