acwing 4645. 选数异或

 输出yes

　　no

　　yes 

　　no

题意分析，给一串数组，再在每次提问时给出一个区间，l,r;

求l,r区间内是否存在两个数，两数异或后值为给出的x；

已知a^b=x-->a^x=b;

思路：1，把每个数异或x，存在另一个数组（b）里，暴力搜索，看区间内b数组内数字是否有等于a数组内数字，TLE

　　2.记录下标，比较每个位置数字可异或为的数字（若存在）的下标，建立数组last[a[i]]记录每个数字（a[i]）在原数组内的下标。

　　g[i]=max(g[i-1],last[a[i]^x])//g[i]=j，存储的是每个位置往左，是否存在它的值异或后的数，若有存它的异或后值的下标，若没有则保存它左边有异或对的下标（靠左边的那个，因为若是右边的就保存在分析右边数字的记录中，所以肯定是左边的）

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],last[(1<<20)+10],g[N];
int main(){
    int n,m,x,l,r;
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        g[i]=max(g[i-1],last[a[i]^x]);
        last[a[i]]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        if(l<=g[r]){
            cout<<"yes"<<endl;
        }else{
            cout<<"no"<<endl;
        }
        
    }
    return 0;
}