标签 倍增 下的文章

「算法笔记」后缀数组

「Codeforces 1143E」Lynyrd Skynyrd

题目链接：Codeforces 1143E

最近 Lynyrd 和 Skynyrd 来到超市购物，Lynyrd 购买了一个长度为 $n$ 的排列 $p$，Skynyrd 购买了一个长度为 $m$ 的包含 $1$ 到 $n$ 的数组 $a$。

他们给你了 $q$ 个询问，每个询问均为如下形式：“在数组 $a$ 的第 $l$ 到 $r$ 个位置之间，是否存在一个子序列满足它是 $p$ 的一个循环位移？”

对于每个询问，如果存在这样的子序列则输出 $1$ 否则输出 $0$。

数据范围：$1\le n, m, q\le 2\times 10 ^ 5$。