好题 P8773 [蓝桥杯 2022 省 A] 选数异或

Wild_Of_The_World · 2025-01-03 21:19:06 · 个人记录

想到了一一对应，但之后去想怎么在区间内表示这关系，然后存在st表中。

但这种关系是很难储存在区间内的，为什么不可以只是记录下来这关系然后再进行运算呢。

我太想单纯地用数据结构去解决这道题，但数据结构本身有着特定的功能，我应该只把它当成一种工具来用。

数据结构不是算法

这道题挺好的，指出了我思维上的这个错误，为什么不能只是记录下这关系？为什么要更复杂地表示在区间内呢？

题解优秀解法：

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20)+5;
int lat[N],n,m,x,a[N];
int f[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i]=max(f[i-1],lat[x^a[i]]);
        lat[a[i]]=i;
    }
    int l,r;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        if(f[r]>=l) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}

st表：

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20)+5;
int lat[N],lst[N],n,m,x,a[N];
int st[N][20],lg[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>x;
    lg[1]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st[i][0]=lat[a[i]^x];
        lat[a[i]]=i;
        if(i!=1) lg[i]=lg[i>>1]+1;
    }
    for(int j=1;j<=lg[n];j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    int l,r,k;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        k=lg[r-l+1];
        if(max(st[l][k],st[r-(1<<k)+1][k])>=l) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}