← 返回题目列表

Codeforces · 1142/B

B. 林纳德·斯金纳德

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

最近 Lynyrd 和 Skynyrd 去了一家商店,Lynyrd 买了一个长度为 $$$n$$$ 的排列 $$$p$$$,Skynyrd 买了一个长度为 $$$m$$$ 的数组 $$$a$$$,由从 $$$1$$$ 到 $$$n$$$ 的整数组成。

Lynyrd 和 Skynyrd 感到无聊,所以他们问你 $$$q$$$ 查询,每个查询都有以下形式:“$$$a$$$ 从第 $$$l$$$ 位置到第 $$$r$$$ 位置(包括在内)的子段是否有一个循环移位 $$$p$$$ 的子序列?请回答疑问。

长度 $$$n$$$ 的排列是 $$$n$$$ 整数的序列,使得从 $$$1$$$ 到 $$$n$$$ 的每个整数在其中恰好出现一次。

排列 $$$(p_1, p_2, \ldots, p_n)$$$ 的循环移位是对某些 $$$i$$$ 的排列 $$$(p_i, p_{i + 1}, \ldots, p_{n}, p_1, p_2, \ldots, p_{i - 1})$$$ $$$1$$$ 到 $$$n$$$。例如,排列 $$$(2, 1, 3)$$$ 具有三个不同的循环移位:$$$(2, 1, 3)$$$、$$$(1, 3, 2)$$$、$$$(3, 2, 1)$$$。

数组 $$$a$$$ 的子段的子序列从第 $$$l$$$ 到第 $$$r$$$ 个位置(含)是一个序列 $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ 对于某些 $$$i_1, i_2, \ldots, i_k$$$ 使得 $$$l \leq i_1 < i_2 < \ldots < i_k \leq r$$$。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$、$$$q$$$ ($$$1 \le n, m, q \le 2 \cdot 10^5$$$) — 排列 $$$p$$$ 的长度、数组 $$$a$$$ 的长度和查询次数。

下一行包含从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 整数,其中第 $$$i$$$ 是排列的第 $$$i$$$ 个元素。从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次。

下一行包含从 $$$1$$$ 到 $$$n$$$ 的 $$$m$$$ 整数,其中第 $$$i$$$ 是数组 $$$a$$$ 的第 $$$i$$$ 个元素。

接下来的 $$$q$$$ 行描述查询。这些行的第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$),这意味着第 $$$i$$$ 查询是关于从第 $$$l_i$$$ 位置到第 $$$r_i$$$ 位置(包括这两个位置)的数组子段。

输出

打印长度为 $$$q$$$ 的单个字符串,由 $$$0$$$ 和 $$$1$$$ 组成,如果数组 $$$a$$$ 从第 $$$l_i$$$ 位置到第 $$$r_i$$$ 位置(含)的子段包含子序列是 $$$p$$$ 的循环移位,否则是 $$$0$$$。

示例

输入 #1

3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5

输出 #1

110

输入 #2

2 4 3
2 1
1 1 2 2
1 2
2 3
3 4

输出 #2

010

注意

在第一个示例中,从 $$$1$$$-st 到 $$$5$$$-th 位置的段是 $$$1, 2, 3, 1, 2$$$。有一个子序列 $$$1, 3, 2$$$ 是置换的循环移位。从第 $$$2$$$-nd 到第 $$$6$$$-th 位置的子段还包含等于该排列的子序列 $$$2, 1, 3$$$。从第 $$$3$$$-rd 到第 $$$5$$$ 个位置的子段是 $$$3, 1, 2$$$,只有一个长度为 $$$3$$$ 的子序列 ($$$3, 1, 2$$$),但它不是置换的循环移位。

在第二个示例中,可能的循环移位是 $$$1, 2$$$ 和 $$$2, 1$$$。从$$$1$$$-st到$$$2$$$-nd位置的子段是$$$1, 1$$$,其子序列不是排列的循环移位。从$$$2$$$-nd到$$$3$$$-rd位置的子段是$$$1, 2$$$,它与排列一致。从$$$3$$$到$$$4$$$位置的子段是$$$2, 2$$$,其子序列不是置换的循环移位。