Codeforces 1142B Lynyrd Skynyrd
题目链接
https://codeforces.com/problemset/problem/1142/B
题目大意
给你一个排列 $P$ 和一个数组 $A$ ，$Q$ 次询问，每次询问 $A$ 在 $[l, r]$ 之间是否存在一个子串，在循环平移之后和 $P$ 相同。
题目分析
定义 $f[i]$ 为数字 $i$ 的最大的出现位置从 $1$ 到 $n$ 进行 $DP$ ，记录下每一个元素在 $P$ 中的前驱的最大出现位置。统计完成之后再使用倍增，处理所有的元素往前找能找到的元素。随后，对于每一个位置，统计出来由它开始往前能构造出来的 $P$ 的最大起始位置。随后 $O(1)$ 查询即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 2e5 + 5;
int n, m, q, t;
int a[maxn];
int b[maxn];
int fa[maxn][20];
int f[maxn];
int ans[maxn];
int last[maxn];
int read(){
int x;
scanf("%d", &x);
return x;
}
int main(){
int i, j;
int l, r;
n = read();
m = read();
q = read();
for(i=1;i<=n;i++){
a[i] = read();
last[a[i]] = a[i - 1];
}
last[a[1]] = a[n];
for(i=1;i<=m;i++){
b[i] = read();
}
for(i=1;i<=m;i++){
fa[i][0] = f[last[b[i]]];
f[b[i]] = i;
}
for(i=1;i<=m;i++){
for(j=0;fa[fa[i][j]][j];j++){
fa[i][j + 1] = fa[fa[i][j]][j];
}
}
for(i=1;i<=m;i++){
ans[i] = i;
int x = n - 1;
for(j=20;j>=0;j--){
if(x >= (1 << j)){
ans[i] = fa[ans[i]][j];
x -= (1 << j);
}
}
ans[i] = max(ans[i], ans[i - 1]);
}
while(q--){
l = read();
r = read();
if(ans[r] >= l){
printf("1");
}else{
printf("0");
}
}
printf("\n");
return 0;
}