P8773 解题报告

Sternenlicht · 2022-11-14 20:41:30 · 题解

思路：

因 x 已给定，所以可以想到预处理。

用一个桶来统计，ansp_i 记录 i 前的数与 A_i 的异或值等于 x 的下标。

由于是区间问题，容易想到用 ST 表解决。在 [l,r] 中，若有 ansp_i \ge l，则有解。所以在 ansp_l 到 ansp_r 之间，取最大值，与 l 相比即可。

#include <bits/stdc++.h>
namespace IO{
    #define LL long long
    inline LL read(){
        LL x=0,f=1;char c=getchar();
        for (;!isdigit(c);c=getchar())if (c=='-')f=-1;
        for (;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
        return x*f;
    }
    inline void write(LL x,char c='\n'){
        if (x){
            if (x<0)x=-x,putchar('-');
            char a[30];short l;
            for (l=0;x;x/=10)a[l++]=x%10^48;
            for (l--;l>=0;l--)putchar(a[l]);
        }else putchar('0');putchar(c);
    }
}using namespace IO;
using namespace std;

const int N = 1e5+10;
const int LogN = 2e1;
int tong[1<<LogN],ansp[N],lg[N],f[N][LogN],n,m,x;
int query(int l,int r)//查询区间值 
{return max(f[l][lg[r-l+1]],f[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);}
int main(){
    n=read(),m=read(),x=read();lg[0]=-1;
    //读入，用tong数组记录标号
    //ansp数组记录 i前的最后一个数与a的异或值等于x 的数的下标 
    for (int i=1,a;i<=n;i++)a=read(),ansp[i]=tong[a^x],tong[a]=i;
    //将ST表数组初始化，log数组初始化 
    for (int i=1;i<=n;i++)f[i][0]=ansp[i],lg[i]=lg[i>>1]+1;
    for (int j=1;j<=LogN;j++)//ST表维护区间最大值 
        for (int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
    for (int i=1,l,r;i<=m;i++){
        l=read(),r=read();
        if (query(l,r)>=l)
            puts("yes");
        else
            puts("no");
    }
    return 0;
}

Update：感谢 @fervency 指正错误。