cf1142 B. Lynyrd Skynyrd（思维，树）

题意：

给定一个长为 n 的排列 a 和一个长为 m 的数组 b。q次询问 \(l,r\)，回答 \(b_l,b_{l+1},\cdots ,b_r\) 中是否包含一个子序列恰是 a 的循环移位。

思路：

贪心，对于每个 \(b_i\)，若有多个 \(b_j\) 可以作为 \(b_i\) 的后继，则只需考虑最左边的那一个（即离 \(b_i\) 最近的那一个）。

构造一个森林，每个点的父结点是它右边的最近后继。

从右往左dfs，每个点只需访问一次。开栈记录往上第n个祖先

\(ri[l] = r\) 表示在 b 中从位置 \(l\) 开始的 a 的循环移位的末尾是 \(r\)。注意若有两个循环移位，其中一个的起点比另一个大但终点比另一个小，则应舍弃另一个。求个后缀最小值即可。

\(O(n)\)

#include 
using namespace std;
const int N = 2e5 + 5;
int n, m, q, a[N], b[N], posa[N], posb[N], vis[N], ri[N];
int h[N], e[N], ne[N], idx;
void add(int a, int b) {
    e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}
int stk[N], tt;
void dfs(int u)
{
    vis[u] = 1; stk[++tt] = u;
    if(tt >= n) ri[u] = stk[tt-n+1];
    for(int i = h[u]; i; i = ne[i])
    {
        int v = e[i];
        if(!vis[v]) dfs(v);
    }
    tt--;
}
signed main()
{
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), posa[a[i]] = i;
    for(int i = 1; i <= m; i++) scanf("%d", &b[i]);

    if(n > 1) a[n + 1] = a[1];

    for(int i = m; i; i--)
    {
        posb[b[i]] = i;
        int nepos = posb[a[ posa[b[i]]+1 ]];
        if(nepos) add(nepos, i);
    }

    memset(ri, 0x3f, sizeof ri);

    for(int i = m; i; i--) if(!vis[i]) dfs(i);

    for(int i = m; i; i--) ri[i] = min(ri[i], ri[i+1]);

    while(q--)
    {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d", ri[l] <= r ? 1 : 0);
    }

    return 0;
}