P97316

校对（proof）

题目描述

小B正在使用一款文字校对软件，检查两行文字是否一致。两行文字都由 n 个小写英文字母组成，分别记为 s 和 t。每一行中的字符位置从左到右编号为 1,2,\ldots,n。

每个位置 i 都有一个给定的差异分值 w_i。检查一段文字时，对于其中每个未被遮挡且两行文字对应字符不同的位置，都将 w_i 计入这次检查的总分。

软件可以暂时遮挡一段位置。一次遮挡会同时作用于两行文字，不会删除字符，也不会改变位置编号。多个遮挡可以重叠；只要一个位置被至少一个当前有效的遮挡覆盖，检查时就不计入这个位置的分值。一次遮挡失效，只会取消这一次遮挡，不会取消其他仍然有效的遮挡。

开始时没有任何遮挡。接下来共有 q 次操作，第 j 次操作发生在时刻 j。操作有以下三种：

  1. 添加遮挡。 给出 l,r,e，遮挡第 l 个位置到第 r 个位置，包括两个端点。这次遮挡从当前时刻开始生效，并在时刻 e 开始时失效，因此不覆盖第 e 次及之后的操作。保证 j。当 e=q+1 时，这次遮挡在剩余的所有操作期间都有效。
  2. 修改字符。 给出 a,p,c，把第 a 行文字的第 p 个字符改成 c。其中 a=1 表示第一行，a=2 表示第二行。即使这个位置正在被遮挡，也可以修改，修改立即生效。遮挡只影响是否计入分值，不会阻止字符的修改。
  3. 检查文字。 给出 l,r，计算第 l 个位置到第 r 个位置中，没有被遮挡且两行对应字符不同的位置的分值总和，包括两个端点。

每个时刻先取消在这一时刻失效的全部遮挡，再执行这一时刻的操作。每个位置的分值 w_i 始终不变。

请依次回答每次检查文字的结果。

输入

第一行包含一个整数 T，表示数据组数。对于每组数据：

第一行包含两个整数 n,q，分别表示每行文字的长度和操作次数。

第二行包含字符串 s，第三行包含字符串 t。

第四行包含 n 个整数 w_1,w_2,\ldots,w_n，表示各个位置的差异分值。

接下来有 q 行，第 j 行描述第 j 次操作。每行第一个整数表示操作类型，格式如下：

  • 1 l r e：添加一次遮挡，含义见题目描述；
  • 2 a p c：把第 a 行文字的第 p 个字符修改为小写英文字母 c；
  • 3 l r：检查第 l 个位置到第 r 个位置，求对应的分值总和。

输出

对于每次类型为 3 的操作，输出一行，包含一个整数，表示这次检查得到的总分。不同数据组的结果之间不需要输出额外的空行。

样例

样例 1

输入

2
5 10
abcde
axcye
2 3 5 7 11
3 1 5
1 2 4 7
1 3 5 9
2 1 3 z
3 1 5
2 2 2 z
3 1 5
2 2 4 d
3 1 5
3 3 5
1 6
a
b
1000000000
1 1 1 3
1 1 1 4
3 1 1
3 1 1
2 2 1 a
3 1 1

输出

10
0
3
8
5
0
1000000000
0

提示

样例解释

第 1 组数据中，开始时只有第 2 个位置和第 4 个位置的字符不同，所以第 1 次操作得到 3+7=10 分。

第 2 次操作遮挡位置 2 至 4，在第 7 次操作开始前失效；第 3 次操作遮挡位置 3 至 5，在第 9 次操作开始前失效。

第 4 次操作把第一行的第 3 个字符改为 z。这个位置虽然正在被遮挡，字符仍然会改变。第 5 次操作检查时，位置 2 至 5 都被遮挡，位置 1 的两个字符相同，所以结果为 0。

第 6 次操作把第二行的第 2 个字符改为 z。第 7 次操作开始前，第一次遮挡失效，但第二次遮挡仍然有效，因此位置 3 至 5 仍被遮挡。只有位置 2 产生分值，结果为 3。

第 8 次操作把第二行的第 4 个字符改为 d。第 9 次操作开始前，第二次遮挡也失效，此时两行文字分别为 abzde 和 azcde。位置 2 和位置 3 的字符不同，第 9 次操作得到 3+5=8 分。第 10 次操作只检查位置 3 至 5，结果为 5。

第 2 组数据中，唯一的位置被先后添加的两次遮挡覆盖。第 3 次操作开始前，只有第一次遮挡失效，第二次遮挡仍然有效，所以结果为 0。第 4 次操作开始前，第二次遮挡也失效，两行字符不同，结果为 10^9。第 5 次操作将第二行字符修改为 a 后，两行字符相同，第 6 次操作得到 0 分。

数据范围与测试点

对于所有数据，保证：

  • 1\le T\le20；
  • 1\le n,q\le2\times10^5；
  • 同一输入文件中，所有数据组的 n 之和不超过 2\times10^5，q 之和也不超过 2\times10^5；
  • 字符串 s,t 的长度都为 n，只包含小写英文字母；
  • 0\le w_i\le10^9；
  • 对于类型为 1、3 的操作，1\le l\le r\le n；
  • 第 j 次操作若属于类型 1，则 j；
  • 对于类型为 2 的操作，a\in{1,2}，1\le p\le n，c 为小写英文字母。

下表中的限制对对应测试点中的每组数据均成立。“—”表示除上述通用数据范围外，没有额外限制。

测试点编号数据规模特殊性质分值
1n,q\le2000—5
2n,q\le2000—5
3n,q\le2000—5
4n,q\le2000—5
5—A5
6—A5
7—B5
8—B5
9—B5
10—C5
11—C5
12—D5
13—D5
14——5
15——5
16——5
17——5
18——5
19——5
20——5

特殊性质 A：没有类型为 1 的操作。

特殊性质 B：所有类型为 1 的操作均满足 l=r。

特殊性质 C：类型为 3 的操作至多出现一次。

特殊性质 D：所有类型为 1 的操作均满足 e=q+1。

每个测试点单独计分，每个测试点为 5 分，总分为 100 分。同一测试点输入文件中的所有查询都回答正确时，获得该测试点的分值。

来源

2026第五届青少年编程挑战精英赛