P8773 题解

Surge_of_Force · 2022-11-13 10:41:38 · 题解

注意到 x 是提前给出的，所以可以考虑预处理

对于每一个 i 我们预处理一个 ans_i 代表 i 前面的最后一个与 A_i 的异或等于 x 的数的下标，这个可以开个桶，边扫边统计。

预处理出这个后，不难发现对于区间 [l,r]，有解的充要条件是存在至少一个 i\in[l,r] 使得 ans_i\ge l，所以只需要对 ans_l 到 ans_r 取个最大值与 l 比较就行了，这个可以线段树 O(n)-(m\log n) 或者 ST 表 O(n\log n)-O(m) 解决，这里用的是 ST 表。

int n,m,x,t[(1ll<<20)+1],ans[MAX],lg[MAX],st[MAX][20];
int ask(int l,int r){
    int len=lg[r-l+1];
    return max(st[l][len],st[r-(1ll<<len)+1][len]);
}
signed main(){
    n=read(),m=read(),x=read();
    for(int i=1;i<=n;i++){
        int xx=read();
        ans[i]=t[xx^x];
        t[xx]=i;
    }
    for(int i=1;i<=n;i++) st[i][0]=ans[i];
    lg[0]=-1;
    for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=20;i++)
        for(int j=1;j+(1ll<<i)-1<=n;j++)
            st[j][i]=max(st[j][i-1],st[j+(1ll<<(i-1))][i-1]);
    while(m--){
        int l=read(),r=read();
        if(ask(l,r)>=l) puts("yes");
        else puts("no"); 
    }
    return 0;
}