#CF2272E. Memory Cell Interception

Memory Cell Interception

题目描述

有两个线程 A\texttt{A} 和 B\texttt{B},以及一个共享内存单元。初始时,内存单元中的值为 00。

线程 A\texttt{A} 有一个长度为 nn 的固定命令序列 ss,线程 B\texttt{B} 有一个长度为 mm 的固定命令序列 tt。每条命令要么是 READ\texttt{READ}(记为 R\texttt{R}),要么是 WRITE\texttt{WRITE}(记为 W\texttt{W})。

每个线程的命令必须按原始顺序执行。然而,两个线程的命令可以任意交错执行。换句话说,实际执行的是将 ss 和 tt 合并得到的一个长度为 n+mn+m 的全局命令序列,且每个字符串内部的命令顺序保持不变。

例如,假设 s=s= RWW\texttt{RWW},t=t= WR\texttt{WR}。

  • 序列 s1,t1,s2,t2,s3s_1,t_1,s_2,t_2,s_3 是一个合法的交错。对应的全局命令序列为 RWWRW\texttt{RWWRW}。
  • 序列 s2,t1,s1,t2,s3s_2,t_1,s_1,t_2,s_3 不是合法的交错,因为 ss 的命令未按原始顺序执行。
  • 序列 s1,t1,s2,t2s_1,t_1,s_2,t_2 不是合法的交错,因为它没有执行所有命令。

全局执行具有时间戳。在任何命令执行之前,时间戳为 00。全局序列中第 ii 个位置执行的命令的时间戳为 ii。

  • 当 WRITE\texttt{WRITE} 命令在时间戳 ii 执行时,它将值 ii 写入共享内存单元。
  • 当 READ\texttt{READ} 命令执行时,它读取共享内存单元中当前存储的时间戳值。

对于 ss 或 tt 中出现的每个 READ\texttt{READ} 命令,求在两个命令序列的所有合法交错下,它能读取到多少种不同的值。

输入格式

每个测试包含多个测试用例。第一行包含测试用例数量 tt(1≤t≤1041 \le t \le 10^4)。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 nn 和 mm(1≤n,m≤2⋅1051 \le n,m \le 2 \cdot 10^5)——分别为线程 A\texttt{A} 和 B\texttt{B} 的命令序列长度。

第二行包含一个长度为 nn 的字符串 ss——线程 A\texttt{A} 的命令序列。

第三行包含一个长度为 mm 的字符串 tt——线程 B\texttt{B} 的命令序列。

ss 和 tt 的每个字符要么是 R\texttt{R} 要么是 W\texttt{W}。字符串 ss 和 tt 各自至少包含一个字符 R\texttt{R}。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5,所有测试用例的 mm 之和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每个测试用例,输出两行。

第一行包含一组整数,表示 ss 中每个 READ\texttt{READ} 指令按顺序对应的答案。该序列的长度必须等于 ss 中字母 R\texttt{R} 的个数。

第二行包含一组整数,表示 tt 中每个 READ\texttt{READ} 指令按顺序对应的答案。该序列的长度必须等于 tt 中字母 R\texttt{R} 的个数。

样例

3
1 1
R
R
1 2
R
WR
3 3
WRW
RWR
1 
1 
2 
2 
4 
3 4 

说明

在第一个样例中,两个 R\texttt{R} 命令都只能读取单元中初始设置的值 00,因此答案均为 11。

在第二个样例中,有 33 种不同的交错方式(红色字母 R\texttt{R} 表示 ss 中的 R\texttt{R}):

  • RWR\mathtt{\color{red}{R}WR}:第一个 R\texttt{R} 读取 00,第二个 R\texttt{R} 读取 22;
  • WRR\mathtt{W\color{red}{R}R}:第一个 R\texttt{R} 读取 11,第二个 R\texttt{R} 读取 11;
  • WRR\mathtt{WR\color{red}{R}}:第一个 R\texttt{R} 读取 11,第二个 R\texttt{R} 读取 11;

综上,两个 R\texttt{R} 命令都可能看到 22 种不同的值。

来源

转载自 Codeforces — Codeforces Round 1130 (Div. 2)。