Codeforces

Luogu

分析

我写个倍增都能写自闭...

考虑你选了一个数之后,下一个数是唯一确定的,而且肯定越靠前越好。

设 $nxt_i$ 表示选了 $a_i$ 之后下一个数选哪个。特别的,如果不存在能选的下一个数,$nxt_i=\infty$。那么我们就相当于要询问 $[l,r]$ 中是否存在一个 $i$ 满足跳 $n-1$ 次 $nxt$ 后跳到的数还在 $[l,r]$ 中。

倍增预处理出一个 $x_i$ 表示每个数跳 $n-1$ 次 $nxt$ 跳到的位置,那么我们只需要知道 $[l,r]$ 内 $x_i$ 的最小值是否在 $[l,r]$ 内即可。这个直接用 ST 表维护就好了。

实际实现的时候为了避免 $\infty$ 的边界问题可以反过来,即设 $nxt_i$ 表示选了 $a_i$ 之后上一个数是哪个(不存在时设为 $0$),然后最小值改成最大值即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,Q;
int a[N],p[N],pos[N];
int lst[N],pre[18][N];
int lg[N],st[18][N];

inline int jump(int x,int y) {
    for (re int i=17;~i;--i)
        if (y&(1<<i)) x=pre[i][x];
    return x;
}
inline int query(int x,int y) {
    int t=lg[y-x+1];
    return max(st[t][x],st[t][y-(1<<t)+1]);
}

int main() {
    n=read(),m=read(),Q=read();
    for (re int i=1;i<=n;++i) pos[p[i]=read()]=i;
    p[0]=p[n];
    for (re int i=1;i<=m;++i) a[i]=read();
    
    if (n>m) {
        while (Q--) putchar('0');
        return 0;
    }

    for (re int i=1;i<=m;++i) pre[0][i]=lst[p[pos[a[i]]-1]],lst[a[i]]=i;
    for (re int i=1;i<18;++i)
        for (re int j=1;j<=m;++j)
            pre[i][j]=pre[i-1][pre[i-1][j]];
    
    for (re int i=2;i<=m;++i) lg[i]=lg[i>>1]+1;
    for (re int i=1;i<=m;++i) st[0][i]=jump(i,n-1);
    for (re int i=1;i<18;++i)
        for (re int j=1;j+(1<<i)-1<=m;++j)
            st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    
    while (Q--) {
        int l=read(),r=read(),t=lg[r-l+1];
        putchar((query(l,r)>=l)+'0');
    }
    return 0;
}
最后修改:2019 年 10 月 17 日 02 : 15 PM