Lynyrd Skynyrd
Contest: Codeforces Round 549 (Div. 1)
Difficulty rating: 2000
Tags: data structures, dfs and similar, dp, math, trees

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$$$.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5

Example output:
110

Example input:
2 4 3
2 1
1 1 2 2
1 2
2 3
3 4

Example output:
010

Editorial:
For each $$$a_i$$$ if the number $$$a_i$$$ has position $$$j$$$ in $$$p$$$, let's find the greatest $$$l$$$, such that $$$l$$$ is less then $$$i$$$ and $$$a_l = p_{j - 1}$$$ (let's define $$$p_0 = p_n$$$) We will call this position $$$b_i$$$. This can be done in $$$O(n)$$$ time, just for each $$$p_j$$$ we will keep the last it's position in $$$a$$$ while iterating over $$$a$$$.
Now let's notice that using this info for each $$$i$$$ we can find the beginning of right most subsequence of $$$a$$$ which is a ciclic shift of $$$p$$$ and ends exactly at $$$a_i$$$. This can easily be done because if there is a subsequence of $$$a$$$ $$$a_{i_1}, a_{i_2} \ldots, a_{i_{n - 1}}, a_i$$$, which is the right most such subsequence, then $$${i_{n - 1}}$$$ is $$$b_i$$$, $$$i_{n- 2}$$$ is $$$b_{i_{n - 1}}$$$, and so on. So to find such subsequence and the position of it's beginning, we need to calculate $$$b[b[b \ldots b[i] \ldots ]]$$$ $$$n - 1$$$ times. To do it we can use binary lifting. Then we will have $$$O(m \log n)$$$ precalc and we will get the beginning of such subsequence in $$$O(\log n)$$$ time.
Now for each prefix of $$$a$$$ let's calculate the the beginning of right most subsequence of it, which is a cyclic shift of $$$p$$$. This can be calculated in linear time, first we look at the answer for this prefix without the last number, and then update it with the right most subsequence, which ends at the end of prefix.
Now we can answer each query in $$$O(1)$$$ time, because we just need to find the beginning of the right most subsequence, which ends at prefix of length $$$r$$$ and compare it with $$$l$$$.