分析性质加无修区间最大。
考虑找到(A)中每个数在(P)中的前驱在(A)中的位置。
那么我们的一个循环移位就相当于是以一个数为开头，向前跳(n-1)步。
倍增求出一个数向前跳(n-1)步的位置，维护一下区间最大值。
如果区间最大(geq L)，就输出(1)，否则为(0)。
其实我们还可以将他看为一棵树，因为没有强制在线，我们就可以用栈(mathcal{O}(n))求出其(n-1)级祖先。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int f=1,w=0;char x=0;
while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
return w*f;
}
const int N=4e5+10;
int n,m,Q;
int A[N],P[N],Las[N],Id[N];
int f[N][25],Max[N][25],Log[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
#endif
n=read(),m=read(),Q=read();
for(int i=1;i<=n;i++) P[i]=read();
for(int i=1;i<=m;i++) A[i]=read();
for(int i=1;i<=n;i++) Las[P[i]]=P[i-1],Las[P[1]]=P[n];
for(int i=2;i<=N-10;i++) Log[i]=Log[i>>1]+1;
for(int i=1;i<=m;i++)
f[i][0]=Id[Las[A[i]]],Id[A[i]]=i;
for(int j=1;j<=Log[n];j++)
for(int i=1;i<=m;i++)
f[i][j]=f[f[i][j-1]][j-1];
for(int i=1;i<=m;i++)
{
int S=0;Max[i][0]=i;
for(int j=Log[n-1];j>=0;j--)
if(S+(1<<j)<=n-1)
Max[i][0]=f[Max[i][0]][j],S+=(1<<j);
}
for(int j=1;j<=Log[m];j++)
for(int i=1;i+(1<<j)-1<=m;i++)
Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
while(Q--)
{
int L=read(),R=read(),X=Log[R-L+1];
int End=max(Max[L][X],Max[R-(1<<X)+1][X]);
End>=L?printf("1"):printf("0");
}
return 0;
}