CF2248D Good Pair Queries

你有两个长度为 $n$ 的二进制串 $s$ 和 $t$。 两个等长的二进制串 $a$ 和 $b$ 被称为好的当且仅当它们可以通过执行以下操作零次或多次后被设置为空： - 选择一组非空的位置 $1\le i_1 \lt i_2 \lt \ldots < i_k \le |a|$ 和一个字符 $c\in \{0,1\}$。 - 令 $x = a_{i_1}a_{i_2}\ldots a_{i_k}$ 且 $y = b_{i_1}b_{i_2}\ldots b_{i_k}$。 - $c$ 同时是 $x$ 和 $y$ 的一个**模式**。 - 删除所有选中的字符，其余字符顺序不变。 一个二进制串可以同时有 $0$ 和 $1$ 作为模式。 你需要回答 $q$ 个问题。每个询问中，你被给出了两个整数 $l$ 和 $r$。请判定 $(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$ 是否是好的。 问题之间是**独立的**。 --- **模式**：我们认为 $c$ 是二进制串 $z$ 的一个模式，当且仅当其在 $z$ 中出现的次数至少为 $z$ 长度的一半（向上取整）。

多测。$t$ ($1\le t\le 10^4$) 组数据。每组数据表述如下。 每组测试数据第一行是两个整数 $n$ 和 $q$ ($1\le n,q\le 2\cdot 10^5$)——串的长度和询问次数。 第二行是长 $n$ 的字符串 $s$。 第二行是长 $n$ 的字符串 $t$。 接下来 $q$ 行每行一个 $l$ 和 $r$ ($1\le l\le r\le n$)——一个询问。 $n$ 的和不超过 $2\cdot 10^5$。 $q$ 的和不超过 $2\cdot 10^5$。

每一行根据 $(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$ 是否是好的回答 “YES” 或 “NO”。 回答大小写不敏感。

第一个样例第一个询问，$(\texttt{0},\texttt{1})$ 不是好的。 第二个询问，选择 $c=\texttt{0}$。然后选择 $x=\texttt{01}$ 且 $y=\texttt{10}$，所以 $c$ 是它们的模式并且整个对被删掉。 第三个样例，$\texttt{00011}$ 和 $\texttt{01111}$ 没有共同的模式，无法在一次操作内清空。它可以在三次操作内清空： - 选择位置 $2$ 和 $4$ 以及 $c=\mathtt{1}$。然后 $x=\mathtt{01}$ 和 $y=\mathtt{11}$，所以 $c$ 是 $x$ 和 $y$ 的模式。在删除选择的位置后，剩下的字符被连接，给出对 $(\mathtt{001},\mathtt{011})$。 - 选择位置 $1$ 和 $2$ 以及 $c=\mathtt{0}$。然后 $x=\mathtt{00}$ 然后 $y=\mathtt{01}$，所以 $c$ 是一个 $x$ 和 $y$ 共同的模式。在删除选定的字符后，对变成了 $(\mathtt{1}, \mathtt{1})$。 - 选择还需处理的位置 $1$ 和 $c=\mathtt{1}$。然后 $x=\mathtt{1}$ 和 $y=\mathtt{1}$，所以 $c$ 是一个 $x$ 和 $y$ 共同的模式。删除选定位置使两个串变空。