[蓝桥杯 2022 省 A] 选数异或 题解 含源码
[蓝桥杯 2022 省 A] 选数异或
题目描述
给定一个长度为 n n n 的数列 A 1 , A 2 , ⋯ , A n A_{1}, A_{2}, \cdots, A_{n} A1,A2,⋯,An 和一个非负整数 x x x, 给定 m m m 次查询, 每次询问能否从某个区间 [ l , r ] [l, r] [l,r] 中选择两个数使得他们的异或等于 x x x 。
输入格式
输入的第一行包含三个整数 n , m , x n, m, x n,m,x 。
第二行包含 n n n 个整数 A 1 , A 2 , ⋯ , A n A_{1}, A_{2}, \cdots, A_{n} A1,A2,⋯,An。
接下来 m m m 行，每行包含两个整数 l i , r i l_{i}, r_{i} li,ri 表示询问区间 [ l i , r i ] \left[l_{i}, r_{i}\right] [li,ri] 。
输出格式
对于每个询问, 如果该区间内存在两个数的异或为 x x x 则输出 yes, 否则输出 no。
样例 #1
样例输入 #1
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
样例输出 #1
yes
no
yes
no
提示
【样例说明】
显然整个数列中只有 2,3 的异或为 1 。
【评测用例规模与约定】
对于 20 % 20 \% 20% 的评测用例, 1 ≤ n , m ≤ 100 1 \leq n, m \leq 100 1≤n,m≤100;
对于 40 % 40 \% 40% 的评测用例, 1 ≤ n , m ≤ 1000 1 \leq n, m \leq 1000 1≤n,m≤1000;
对于所有评测用例, 1 ≤ n , m ≤ 1 0 5 , 0 ≤ x < 2 20 , 1 ≤ l i ≤ r i ≤ n 1 \leq n, m \leq 10^5,0 \leq x<2^{20}, 1 \leq l_{i} \leq r_{i} \leq n 1≤n,m≤105,0≤x<220,1≤li≤ri≤n ， 0 ≤ A i < 2 20 0 \leq A_{i}<2^{20} 0≤Ai<220 。
蓝桥杯 2022 省赛 A 组 D 题。
#include<bits/stdc++.h>
using namespace std;
long long q,w,e,r,t,a,y,u,i,o,p,d,f,g,h,j,k,l,z,x,c,v,b,n,m;
long long s,aa[100005],bb[100005],cc[10][100005],last[100005];
int main()
{cin>>n>>m>>x; for(i=1;i<=n;i++){cin>>aa[i];bb[i]=max(bb[i-1],last[aa[i]^x]);last[aa[i]]=i;}for(i=1;i<=m;i++){cin>>p>>q;if(bb[q]<p) cout<<"no"<<endl;else cout<<"yes"<<endl;}return 0;
}