← 返回题目列表

Codeforces · 1320/D

D. 可到达的字符串

中文机器翻译题面 查看原题

在这个问题中,我们将处理二进制字符串。二进制字符串的每个字符要么是 0,要么是 1。我们还将处理子字符串;回想一下,子字符串是字符串的连续子序列。我们将字符串 $$$s$$$ 中从第 $$$l$$$ 个字符开始到第 $$$r$$$ 个字符结束的子串表示为 $$$s[l \dots r]$$$。每个字符串的字符从$$$1$$$开始编号。

我们可以对我们考虑的字符串执行多种操作。每个操作都是选择字符串的一个子字符串并将其替换为另一个字符串。有两种可能的操作类型:将 011 替换为 110,或将 110 替换为 011。例如,如果我们对字符串 110011110 执行一次操作,则可以将其转换为 011011110、110110110 或 110011011。

如果存在序列 $$$s_1$$$, $$$s_2$$$, ..., $$$s_k$$$ 使得 $$$s_1 = a$$$, $$$s_k = b$$$,并且对于每个 $$$i \in [1, k - 1]$$$, $$$s_i$$$ 可以通过一次操作转换为 $$$s_{i + 1}$$$。请注意,$$$k$$$ 可以等于 $$$1$$$,i。即,每个字符串都可以从其自身到达。

给你一个字符串 $$$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 \cdot 10^5$$$) — 字符串 $$$t$$$ 的长度。

第二行包含一个字符串 $$$t$$$ ($$$|t| = n$$$)。 $$$t$$$ 的每个字符不是 0 就是 1。

第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数量。

接下来是 $$$q$$$ 行,每行代表一个查询。第 $$$i$$$ 行包含第 $$$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$$$)。

输出

对于每个查询,如果 $$$t[l_1 \dots l_1 + len - 1]$$$ 可从 $$$t[l_2 \dots l_2 + len - 1]$$$ 访问,则打印 YES,否则打印 NO。您可以在任何寄存器中打印每个字母。

示例

输入 #1

5
11011
3
1 3 3
1 4 2
1 2 3

输出 #1

Yes
Yes
No