问题描述
Recently Lynyrd and Skynyrd went to a shop where Lynyrd bought a permutation p of length n, and Skynyrd bought an array a of length mm, consisting of integers from 1 to n.
Lynyrd and Skynyrd became bored, so they asked you q queries, each of which has the following form: "does the subsegment of a from the l-th to the r-th positions, inclusive, have a subsequence that is a cyclic shift of p?" Please answer the queries.
A permutation of length n is a sequence of n integers such that each integer from 1 to n appears exactly once in it.
A cyclic shift of a permutation (p1,p2,…,pn) is a permutation (pi,pi+1,…,pn,p1,p2,…,pi−1)for some ii from 1 to n. For example, a permutation (2,1,3) has three distinct cyclic shifts: (2,1,3), (1,3,2), (3,2,1).
A subsequence of a subsegment of array a from the l-th to the r-th positions, inclusive, is a sequence ai1,ai2,…,aik for some i1,i2,…,i such that l≤i1<i2<…<ik≤r.
输入格式
The first line contains three integers n , m , q(( 1 le n, m, q le 2 cdot 10^5 )) — the length of the permutation p , the length of the array a and the number of queries.
The next line contains n integers from 1 to n , where the i-th of them is the i -th element of the permutation. Each integer from 1 to n appears exactly once.
The next line contains m integers from 1 to n, the i -th of them is the i-th element of the array a .
The next q lines describe queries. The i -th of these lines contains two integers li and ri ($ 1 le l_i le r_i le m )$, meaning that the i -th query is about the subsegment of the array from the li-th to the ri-th positions, inclusive.
输出格式
Print a single string of length q , consisting of 0 and 1 , the digit on the i -th positions should be 1 , if the subsegment of array a from the li-th to the ri-th positions, inclusive, contains a subsequence that is a cyclic shift of p , and 0 otherwise.
题目翻译
解析
可以观察到一个性质：一个循环排列除了开头的元素，其余元素前面是哪个数是唯一的。所以，我们利用这一点，设(to[i])表示元素i在排列中的下一个数是什么。如果i是最后一个，(to[i])就是第一个。对于原来的序列a的每一个元素(a[i])，都从后面最近的(to[a[i]])的位置向i连一条有向边。位置最近是为了保证回答询问时尽可能的合法。
可以发现，最后得到的是一个森林。只要从根节点遍历每一棵树，用一个栈记录当前在递归中的点。如果点的数量大于等于 n，说明找到了一个合法的循环排列，开头的位置是(s[top-n+1])，那么离开头最近的循环排列的结束位置就是当前点。
有了这些信息，我们可以回答每一个询问了。记(minp[i])表示以i为起点的循环排列最近的结束位置。对minp做后缀最小值，那么(minp[i])就表示i之后最近的循环排列结束在哪里。对于每个询问，只要看(minp[l])是否小于等于(r)即可。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 200002
using namespace std;
int head[N],ver[N*2],nxt[N*2],l;
int n,m,q,i,p[N],a[N],minp[N],pos[N],to[N],top,s[N];
bool vis[N];
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
void insert(int x,int y)
{
l++;
ver[l]=y;
nxt[l]=head[x];
head[x]=l;
}
void dfs(int x)
{
vis[x]=1;
s[++top]=x;
if(top>=n) minp[x]=s[top-n+1];
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(!vis[y]) dfs(y);
}
top--;
}
int main()
{
n=read();m=read();q=read();
for(i=1;i<=n;i++) p[i]=read();
for(i=1;i<=m;i++) a[i]=read();
for(i=1;i<=n;i++) to[p[i]]=p[i%n+1];
for(i=m;i>=1;i--){
if(pos[a[i]]==0||pos[a[i]]>i) pos[a[i]]=i;
if(pos[to[a[i]]]!=0){
insert(pos[to[a[i]]],i);
}
}
memset(minp,0x3f,sizeof(minp));
for(i=m;i>=1;i--){
if(!vis[i]) dfs(i);
}
for(i=m-1;i>=1;i--) minp[i]=min(minp[i],minp[i+1]);
for(i=1;i<=q;i++){
int l=read(),r=read();
if(minp[l]<=r) printf("1");
else printf("0");
}
return 0;
}