题目链接：Codeforces 1143E

最近 Lynyrd 和 Skynyrd 来到超市购物，Lynyrd 购买了一个长度为 $n$ 的排列 $p$，Skynyrd 购买了一个长度为 $m$ 的包含 $1$ 到 $n$ 的数组 $a$。

他们给你了 $q$ 个询问，每个询问均为如下形式：“在数组 $a$ 的第 $l$ 到 $r$ 个位置之间，是否存在一个子序列满足它是 $p$ 的一个循环位移？”

对于每个询问，如果存在这样的子序列则输出 $1$ 否则输出 $0$。

数据范围：$1\le n, m, q\le 2\times 10 ^ 5$。

Solution

我们首先贪心：如果第 $i$ 个位置匹配了，那么它前一个匹配的位置一定是距离它最近的合法位置。

于是我们得到了一个朴素算法：对于 $l, r$ 里的每个数暴力往前跳，如果有任何一个数跳完 $n - 1$ 步还在区间 $[l, r]$ 内那么有解；否则无解。

接下来考虑优化这个过程。我们先不考虑区间内每个数都往前跳，只考虑第 $i$ 个数往前跳 $n - 1$ 个数的位置，这个过程可以通过倍增实现。

最后考虑区间每个数。我们用 $\text{RMQ}$ 维护区间每个数往前跳 $n - 1$ 步的最大位置，判断这个位置是否不小于 $l$ 即可。

时间复杂度：$\mathcal O(m\log n + n + q)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 2e5 + 5, logN = 18;

int n, m, q, p[N], a[N], pos[N], pre[N], lg[N], f[N][logN], g[N][logN];

int query(int l, int r) {
    int k = lg[r - l + 1];
    return std::max(g[l][k], g[r - (1 << k) + 1][k]);
}
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        pos[p[i]] = i;
    }
    p[0] = p[n];
    for (int i = 1; i <= m; i++) {
        scanf("%d", &a[i]);
        int x = p[pos[a[i]] - 1];
        f[i][0] = pre[x], pre[a[i]] = i;
    }
    for (int j = 1; (1 << j) <= 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 l = n - 1, p = i;
        for (int j = 17; ~j; j--) {
            if (l & (1 << j)) p = f[p][j];
        }
        g[i][0] = p;
    }
    for (int i = 2; i <= m; i++) lg[i] = lg[i >> 1] + 1;
    for (int j = 1; (1 << j) <= m; j++) {
        for (int i = 1; i + (1 << j) - 1 <= m; i++) {
            g[i][j] = std::max(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1; i <= q; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        putchar((query(l, r) >= l) + '0');
    }
    puts("");
    return 0;
}