Lynyrd Skynyrd (Codeforces 1142B)
Tags: 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: 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: 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.

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.

Sample Inputs:
3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5

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

Sample Outputs:
110

010

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m, q) = map(int, input().split())
p = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
pr = [0] * (n + 1)
for i in range(n):
    pr[p[(i + 1) % n]] = p[i]
u = [[] for _ in range(n + 1)]
inf = pow(10, 9) + 1
dp = [inf] * (m + 1)
for i in range(1, m + 1):
    ai = a[i]
    u[ai].append(i)
    j = pr[ai]
    uj = u[j]
    l = len(uj)
    for _ in range(l):
        dp[uj.pop()] = i
nx = [i for i in range(m + 1)]
v = n - 1
for _ in range(20):
    if not v:
        break
    if v & 1:
        for i in range(1, m + 1):
            if nx[i] ^ inf:
                nx[i] = dp[nx[i]]
    dp = [inf if dp[i] == inf else dp[dp[i]] for i in range(m + 1)]
    v >>= 1
for i in range(m - 1, 0, -1):
    nx[i] = min(nx[i], nx[i + 1])
ans = []
for _ in range(q):
    (l, r) = map(int, input().split())
    ans0 = '1' if nx[l] <= r else '0'
    ans.append(ans0)
sys.stdout.write(''.join(ans))

Solution (Python):
import os
from io import BytesIO, StringIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def input_as_list():
    return list(map(int, input().split()))

def array_of(f, *dim):
    return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()

def main():
    (n, m, q) = input_as_list()
    p = input_as_list()
    a = input_as_list()
    if n == 1:
        print('1' * q)
        return
    next_p = array_of(int, n)
    next_a = array_of(int, m)
    prev = p[-1] - 1
    for pi in p:
        pi -= 1
        next_p[prev] = pi
        prev = pi
    idx_a = array_of(int, n)
    for i in range(len(a) - 1, -1, -1):
        ai = a[i] - 1
        next_a[i] = idx_a[next_p[ai]]
        idx_a[ai] = i
    ep = array_of(int, m)
    parent = next_a
    children = array_of(list, m)
    roots = []
    for (i, p) in enumerate(parent):
        if p == 0:
            roots.append(i)
        else:
            children[p].append(i)
    rank = array_of(int, m)
    parent_ex = array_of(list, m)
    for r in roots:
        stack = [r]
        while stack:
            p = stack.pop()
            for c in children[p]:
                rank[c] = rank[p] + 1
                parent_ex[c].append(p)
                i = 1
                while 2 ** i <= rank[c]:
                    parent_ex[c].append(parent_ex[parent_ex[c][-1]][i - 1])
                    i += 1
                stack.append(c)
    for i in range(m):
        y = i
        s = 0
        try:
            for j in reversed(range(20)):
                if n - s - 1 >= 2 ** j:
                    y = parent_ex[y][j]
                    s += 2 ** j
            ep[i] = y
        except IndexError:
            pass
    mn = 200000
    flag = False
    for i in range(len(ep) - 1, -1, -1):
        epi = ep[i]
        if epi != 0:
            if epi > mn:
                ep[i] = mn
            mn = min(mn, epi)
            flag = True
        elif flag:
            ep[i] = mn
    out = []
    for _ in range(q):
        (l, r) = map(int, input().split())
        (l, r) = (l - 1, r - 1)
        if ep[l] == 0 or ep[l] > r:
            out.append('0')
        else:
            out.append('1')
    print(''.join(out))
main()

Solution (Python):
import os
from io import BytesIO, StringIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def input_as_list():
    return list(map(int, input().split()))

def array_of(f, *dim):
    return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()

def main():
    (n, m, q) = input_as_list()
    p = input_as_list()
    a = input_as_list()
    if n == 1:
        print('1' * q)
        return
    next_p = array_of(int, n)
    next_a = array_of(int, m)
    prev = p[-1] - 1
    for pi in p:
        pi -= 1
        next_p[prev] = pi
        prev = pi
    idx_a = array_of(int, n)
    for i in range(len(a) - 1, -1, -1):
        ai = a[i] - 1
        next_a[i] = idx_a[next_p[ai]]
        idx_a[ai] = i
    ep = array_of(int, m)
    parent = next_a
    children = array_of(list, m)
    roots = []
    for (i, p) in enumerate(parent):
        if p == 0:
            roots.append(i)
        else:
            children[p].append(i)
    rank = array_of(int, m)
    parent_ex = array_of(list, m)
    for r in roots:
        stack = [r]
        while stack:
            p = stack.pop()
            for c in children[p]:
                rank[c] = rank[p] + 1
                parent_ex[c].append(p)
                i = 1
                while 2 ** i <= rank[c]:
                    parent_ex[c].append(parent_ex[parent_ex[c][-1]][i - 1])
                    i += 1
                stack.append(c)
    for i in range(m):
        y = i
        s = 0
        try:
            for j in reversed(range(20)):
                if n - s - 1 >= 2 ** j:
                    y = parent_ex[y][j]
                    s += 2 ** j
            ep[i] = y
        except IndexError:
            pass
    mn = 200000
    flag = False
    for i in range(len(ep) - 1, -1, -1):
        epi = ep[i]
        if epi != 0:
            if epi > mn:
                ep[i] = mn
            mn = min(mn, epi)
            flag = True
        elif flag:
            ep[i] = mn
    out = []
    for _ in range(q):
        (l, r) = map(int, input().split())
        (l, r) = (l - 1, r - 1)
        if ep[l] == 0 or ep[l] > r:
            out.append('0')
        else:
            out.append('1')
    print(''.join(out))
main()