Lynyrd Skynyrd

*题目名称：Lynyrd 与 Skynyrd* ## 题目描述 最近 Lynyrd 和 Skynyrd 去了一个商店，在那里 Lynyrd 买了一个长度为$n$的排列$p$，Skynyrd 买了一个一个长度为$m$的数列$a$，并且$a_i \in[1,n], a_i \in Z$。 Lynyrd 和 Skynyrd 感到无聊，所以他们给了你$q$个询问，每个询问格式如同：“$a$的**子段**$[l, r]$是否有一个**子序列**$s$，满足$s$是$p$的一个循环移位？”请你回答这些询问。 一个长度为$n$的*排列*是一个由$n$个整数组成的序列，满足从$1$到$n$的所有整数在其中恰好出现$1$次。 一个排列$(p_1, p_2, \ldots, p_n)$的*循环移位*是排列$(p_i, p_{i+1}, \ldots, p_n, p_1, p_2, \ldots, p_{i-1})$，其中$i \in [1, n]$。例如：排列$(2, 1, 3)$有$3$个显然的循环移位：$(2, 1, 3); (1, 3, 2); (3, 2, 1)$。 一个序列$a$的子段$[l, r]$的*子序列*是一个序列$a_{i_1}, a_{i_2}, \ldots a_{i_k}$，其中$l \leq i_1 < i_2 < \ldots < i_k \leq r$。 ## 输入输出格式 ### 输入格式： 输入文件的第一行包含$3$个整数$n, m, q \ (1 \leq n, m, q \leq 2 \times 10^5)$ —— 排列$p$的长度，序列$a$的长度和询问的个数。 接下来一行包含$n$个整数，第$i$个整数表示排列$p$的元素$p_i$。保证$[1, n]$中的每个整数恰好出现$1$次。 接下来一行包含$m$个整数，第$i$个整数表示数列$a$的元素$a_i$。保证$a_i \in [1, n]$。 接下来$q$行每行描述一组询问。这$q$行中的第$i$行包含两个整数$l_i$和$r_i$$(1 \leq l_i \leq r_i \leq m)$，表示第$i$个询问是关于$a$的子段$[l, r]$的。 ### 输出格式： 输出文件仅包含一个由`0`或`1`组成的长度为$q$的字符串，字符串的第$i$位表示第$i$次询问的结果：`0`表示不存在，`1`表示存在。 ## 说明 样例1中子段$[1, 5]$是$\underline1, 2, \underline3, 1, \underline2$，它包含的一个子序列$1, 3, 2$是给定排列的一个循环移位；子段$[2, 6]$包含的子序列$2, 1, 3$与给定排列等价；子段$[3, 5]$只有一个长度为$3$的子序列$3, 1, 2$，但是这不是给定序列的循环移位。 样例2中所有可能的循环移位是$1, 2$和$2, 1$。子段$[1, 2]$是$1, 1$，不包含任何循环移位；子段$[2, 3]$是$1, 2$，是一个循环移位；子段$[3, 4]$是$2, 2$，它的所有子段中没有一个是给定排列的循环移位。

Recently Lynyrd and Skynyrd went to a shop where Lynyrd bought a permutation $ p $ of length $ n $ , and Skynyrd bought an array $ a $ of length $ m $ , consisting of integers from $ 1 $ to $ n $ . Lynyrd and Skynyrd became bored, so they asked you $ q $ queries, each of which has the following form: "does the subsegment of $ a $ from the $ l $ -th to the $ r $ -th positions, inclusive, have a subsequence that is a cyclic shift of $ p $ ?" Please answer the queries. A permutation of length $ n $ is a sequence of $ n $ integers such that each integer from $ 1 $ to $ n $ appears exactly once in it. A cyclic shift of a permutation $ (p_1, p_2, \ldots, p_n) $ is a permutation $ (p_i, p_{i + 1}, \ldots, p_{n}, p_1, p_2, \ldots, p_{i - 1}) $ for some $ i $ from $ 1 $ to $ n $ . For example, a permutation $ (2, 1, 3) $ has three distinct cyclic shifts: $ (2, 1, 3) $ , $ (1, 3, 2) $ , $ (3, 2, 1) $ . A subsequence of a subsegment of array $ a $ from the $ l $ -th to the $ r $ -th positions, inclusive, is a sequence $ a_{i_1}, a_{i_2}, \ldots, a_{i_k} $ for some $ i_1, i_2, \ldots, i_k $ such that $ l \leq i_1 < i_2 < \ldots < i_k \leq r $ .

The first line contains three integers $ n $ , $ m $ , $ q $ ( $ 1 \le n, m, q \le 2 \cdot 10^5 $ ) — the length of the permutation $ p $ , the length of the array $ a $ and the number of queries. The next line contains $ n $ integers from $ 1 $ to $ n $ , where the $ i $ -th of them is the $ i $ -th element of the permutation. Each integer from $ 1 $ to $ n $ appears exactly once. The next line contains $ m $ integers from $ 1 $ to $ n $ , the $ i $ -th of them is the $ i $ -th element of the array $ a $ . The next $ q $ lines describe queries. The $ i $ -th of these lines contains two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le m $ ), meaning that the $ i $ -th query is about the subsegment of the array from the $ l_i $ -th to the $ r_i $ -th positions, inclusive.

Print a single string of length $ q $ , consisting of $ 0 $ and $ 1 $ , the digit on the $ i $ -th positions should be $ 1 $ , if the subsegment of array $ a $ from the $ l_i $ -th to the $ r_i $ -th positions, inclusive, contains a subsequence that is a cyclic shift of $ p $ , and $ 0 $ otherwise.

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

110

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

010

In the first example the segment from the $ 1 $ -st to the $ 5 $ -th positions is $ 1, 2, 3, 1, 2 $ . There is a subsequence $ 1, 3, 2 $ that is a cyclic shift of the permutation. The subsegment from the $ 2 $ -nd to the $ 6 $ -th positions also contains a subsequence $ 2, 1, 3 $ that is equal to the permutation. The subsegment from the $ 3 $ -rd to the $ 5 $ -th positions is $ 3, 1, 2 $ , there is only one subsequence of length $ 3 $ ( $ 3, 1, 2 $ ), but it is not a cyclic shift of the permutation. In the second example the possible cyclic shifts are $ 1, 2 $ and $ 2, 1 $ . The subsegment from the $ 1 $ -st to the $ 2 $ -nd positions is $ 1, 1 $ , its subsequences are not cyclic shifts of the permutation. The subsegment from the $ 2 $ -nd to the $ 3 $ -rd positions is $ 1, 2 $ , it coincides with the permutation. The subsegment from the $ 3 $ to the $ 4 $ positions is $ 2, 2 $ , its subsequences are not cyclic shifts of the permutation.