CF1320D Reachable Strings

在本题中，我们将处理二进制字符串。二进制字符串的每个字符要么是 $0$，要么是 $1$。我们还会涉及子串；回忆一下，子串是字符串的一个连续子序列。我们用 $s[l \dots r]$ 表示字符串 $s$ 从第 $l$ 个字符开始到第 $r$ 个字符结束的子串。每个字符串的字符编号从 $1$ 开始。 我们可以对这些字符串进行若干操作。每次操作可以选择字符串的一个子串，并将其替换为另一个字符串。操作有两种类型：将 $011$ 替换为 $110$，或者将 $110$ 替换为 $011$。例如，如果我们对字符串 $110011110$ 执行一次操作，它可以被变换为 $011011110$、$110110110$ 或 $110011011$。 如果存在一系列字符串 $s_1, s_2, \ldots, s_k$，使得 $s_1 = a$，$s_k = b$，并且对于每个 $i \in [1, k-1]$，$s_i$ 可以通过恰好一次操作变换为 $s_{i+1}$，那么我们称二进制字符串 $a$ 可以到达二进制字符串 $b$。注意，$k$ 可以等于 $1$，即每个字符串都可以到达自身。 现在给定一个字符串 $t$ 和 $q$ 个关于它的询问。每个询问包含三个整数 $l_1$、$l_2$ 和 $len$。对于每个询问，你需要判断 $t[l_1 \dots l_1 + len - 1]$ 是否可以通过若干次操作从 $t[l_2 \dots l_2 + len - 1]$ 变换得到。

第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）——字符串 $t$ 的长度。 第二行包含一个字符串 $t$（$|t| = n$）。$t$ 的每个字符都是 $0$ 或 $1$。 第三行包含一个整数 $q$（$1 \le q \le 2 \times 10^5$）——询问的数量。 接下来 $q$ 行，每行表示一个询问。第 $i$ 行包含三个整数 $l_1$、$l_2$ 和 $len$（$1 \le l_1, l_2 \le |t|$，$1 \le len \le |t| - \max(l_1, l_2) + 1$），表示第 $i$ 个询问。

对于每个询问，如果 $t[l_1 \dots l_1 + len - 1]$ 可以通过若干次操作从 $t[l_2 \dots l_2 + len - 1]$ 变换得到，输出 YES，否则输出 NO。你可以用任意大小写输出每个字母。

由 ChatGPT 4.1 翻译