CF2210D A Simple RBS Problem

一个括号序列被称为正规括号序列（RBS），如果可以通过在该序列中插入字符 $+$ 和 $1$ 得到一个正确的算术表达式。例如，序列 (())()、() 和 (()(())) 是正规括号序列，而 )(、(() 和 (()))( 不是。我们把正规括号序列简称为 RBS。 对于任意一个 RBS 字符串 $b$，你可以进行如下操作： - 选择 $b$ 的任意两个不相交、非空的 RBS 子串，将这两个子串交换位置。 更正式地说，设 $b$ 长度为 $m$，你可以进行如下操作： - 选择索引 $1 \le l_1 < r_1 < l_2 < r_2 \le m$，使得子串 $b[l_1..r_1]$ 和 $b[l_2..r_2]$ 都是 RBS，然后交换这两个子串。操作后，$b$ 变为 $b_1 \ldots b_{l_1-1} b_{l_2} b_{l_2+1}\ldots b_{r_2} b_{r_1+1}\ldots b_{l_2-1} b_{l_1} b_{l_1+1}\ldots b_{r_1}b_{r_2+1} \ldots b_m$。 现在，给定两个长度为 $n$（$n$ 是偶数）的字符串 $s$ 和 $t$，其中 $s$ 和 $t$ 都是 RBS。 请你判断是否可以通过上述操作若干次，将 $s$ 变换为 $t$。 $^{\text{∗}}$ 字符串 $a$ 是字符串 $b$ 的子串，如果 $a$ 可以通过从 $b$ 中删除若干（可以为零或全部）个开头和结尾的字符得到。

每组测试包含多组测试数据。第一行为测试用例数量 $t$（$1 \le t \le 10^4$）。 每组测试数据的第一行包含一个整数 $n$（$4\leq n\leq 5\cdot 10^5$，$n$ 是偶数）。 第二行是一串长度为 $n$ 的字符串 $s$，保证 $s$ 是 RBS。 第三行是一串长度为 $n$ 的字符串 $t$，保证 $t$ 是 RBS。 保证所有测试数据中 $n$ 的总和不超过 $5\cdot 10^5$。

对于每组测试数据，如果可以将 $s$ 变成 $t$，输出 "YES"，否则输出 "NO"。 输出不区分大小写。例如，"yEs"、"yes"、"Yes" 和 "YES" 都被认为是肯定的回应。

在第一个测试用例中，两个字符串已经相同。 在第三个测试用例中，可以选择 $l_1=1, r_1=4, l_2=5, r_2=6$，将 $s$ 变成 $t$。 下图显示了该操作的过程： $\color{red}{(())}\color{blue}{()}\rightarrow\color{blue}{()}\color{red}{(())}$ 由 ChatGPT 5 翻译