B. Lynyrd Skynyrd

传送门：

题意：给出 n,m,q

然后给出模板串，从1-n数字只出现一次，然后给出长度为m的要询问的串。

q组询问：每组询问输出 ‘1’或者‘0’

每组询问 一对x,y    问在x到y中有没有模板串通过循环移动得到的串

(2,1,3)--> (3,2,1)-->(1,3,2)

题解：我们在给出的模板串时，标记这个数字出现的位置。

然后做一个1-m的循环 去找 每个数字的前缀连起来。

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define re register

const int N=1e6+;

void read(int &a)

{

    a=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar());

    for(;isdigit(ch);ch=getchar())

        a=(a<<)+(a<<)+(ch^);

}

int n,m,q;

int w1[N],w2[N],ww1[N];

int t[N],gnd[N][],len[N];///t[i]=j表示原序列中的位置出现的第二组串的最后位置,gnd[i][j]记录i位置前是当前数字的前缀的数的位置

int ans[N];

int main()

{

    read(n);

    read(m);

    read(q);

    for(re int i=;i<=n;i++)

        read(w1[i]),ww1[w1[i]]=i;///w1存模板串,ww1存数字的位置

    for(re int i=;i<=m;i++)

    {

        read(w2[i]);

        w2[i]=ww1[w2[i]];///取得该数字在模板串中的位置

        int lst=w2[i]-;

        if(!lst)

            lst=n;

        if(t[lst])

            gnd[i][]=t[lst],len[i]=len[t[lst]]+;///len[i]记录在该位置找前缀能连续找几个

        else

            len[i]=;

        t[w2[i]]=i;

        for(re int j=;j<&&gnd[i][j-];j++)

            gnd[i][j]=gnd[gnd[i][j-]][j-];

        if(len[i]>=n)///如果能连续找到的前缀大于等于n时,明显就要去找最短区间

        {

            lst=i;

            for(re int j=;j<;j++)

                if(((n-)>>j)&)

                    lst=gnd[lst][j];///倍增上去最前面的,目的得到以这个点最短的满足的区间

            ans[i]=lst;

        }

        ans[i]=max(ans[i],ans[i-]);///ans[i]表示在i位置满足条件的最大起始点

    }

    int x,y;

    while(q--)

    {

        read(x);

        read(y);

        putchar(ans[y]>=x?'':'');

    }

    return ;

}