---恢复内容开始---
题意：给你一个排列p和数组a，有t组询问，每次询问一个区间的子序列中是否有p的一个循环排列。
思路：以p = [3, 1, 2]举例， 我们扫描数组b，假设当前数字是1,那么我们找前面离现在最近的3的位置，然后连一条边。为什么只连最近的呢？比如[3,3,1,2]这种情况，1只需要和第二个3连就行了，因为连第一个3的这种情况已经被连第二个3的这种情况包含了。那么对于每个点，我们可以找到通过连的边走n - 1次所到的点，所有包含这个区间的询问区间都有一个合法的循环排列。但是直接暴力找n - 1次到的点会被卡成O(n^2)的，我们可以用倍增优化这个过程。之后，对于每个点，我们只需记录在它前面的点中满足走n - 1次的点中最大的那一个就行了，因为这样相当于对于每个点，尽力压缩合法的区间。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int f[maxn][20], pre[maxn], a[maxn], b[maxn], last[maxn], p[maxn], res[maxn];
int n, m, T, t;
int solve(int x) {
int now = n - 1, ans = x;
for (int i = t; i >= 0; i--) {
if(p[i] <= now) {
ans = f[ans][i];
now -= p[i];
}
}
return ans;
}
int main() {
int l, r;
scanf("%d%d%d", &n, &m, &T);
t = (int)(log(n) / log(2)) + 1;
p[0] = 1;
for (int i = 1; i <= t;i++) {
p[i] = p[i - 1] * 2;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 2; i <= n; i++) {
pre[a[i]] = a[i - 1];
}
pre[a[1]] = a[n];
for (int i = 1; i <= m; i++) {
scanf("%d", &b[i]);
f[i][0] = last[pre[b[i]]];
for (int j = 1; j <= t; j++) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
last[b[i]] = i;
}
int pos;
for (int i = 1; i <= m; i++) {
pos = solve(i);
res[i] = max(res[i - 1], pos);
}
while(T--) {
scanf("%d%d", &l, &r);
if(res[r] >= l) printf("1");
else printf("0");
}
}
---恢复内容结束---