题意：给出 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+10; void read(int &a) { a=0; char ch=getchar(); for(;!isdigit(ch);ch=getchar()); for(;isdigit(ch);ch=getchar()) a=(a<<3)+(a<<1)+(ch^48); } int n,m,q; int w1[N],w2[N],ww1[N]; int t[N],gnd[N][18],len[N];///t[i]=j表示原序列中的位置出现的第二组串的最后位置,gnd[i][j]记录i位置前是当前数字的前缀的数的位置 int ans[N]; int main() { read(n); read(m); read(q); for(re int i=1;i<=n;i++) read(w1[i]),ww1[w1[i]]=i;///w1存模板串,ww1存数字的位置 for(re int i=1;i<=m;i++) { read(w2[i]); w2[i]=ww1[w2[i]];///取得该数字在模板串中的位置 int lst=w2[i]-1; if(!lst) lst=n; if(t[lst]) gnd[i][0]=t[lst],len[i]=len[t[lst]]+1;///len[i]记录在该位置找前缀能连续找几个 else len[i]=1; t[w2[i]]=i; for(re int j=1;j<18&&gnd[i][j-1];j++) gnd[i][j]=gnd[gnd[i][j-1]][j-1]; if(len[i]>=n)///如果能连续找到的前缀大于等于n时,明显就要去找最短区间 { lst=i; for(re int j=0;j<18;j++) if(((n-1)>>j)&1) lst=gnd[lst][j];///倍增上去最前面的,目的得到以这个点最短的满足的区间 ans[i]=lst; } ans[i]=max(ans[i],ans[i-1]);///ans[i]表示在i位置满足条件的最大起始点 } int x,y; while(q--) { read(x); read(y); putchar(ans[y]>=x?'1':'0'); } return 0; }