问题描述
给定一个长度为 �n 的数列 �1,�2,⋯,��A1,A2,⋯,An 和一个非负整数 �x, 给定 �m 次查 询, 每次询问能否从某个区间 [�,�][l,r] 中选择两个数使得他们的异或等于 �x 。
输入格式
输入的第一行包含三个整数 �,�,�n,m,x 。
第二行包含 �n 个整数 �1,�2,⋯,��A1,A2,⋯,An 。
接下来 �m 行,每行包含两个整数 ��,��li,ri 表示询问区间 [��,��][li,ri] 。
输出格式
对于每个询问, 如果该区间内存在两个数的异或为 �x 则输出 yes, 否则输出 no。
样例输入
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
样例输出
yes
no
yes
no
样例说明
显然整个数列中只有 22, 33 的异或为 11。
评测用例规模与约定
对于 2020 的评测用例, 1≤�,�≤1001≤n,m≤100;
对于 4040 的评测用例, 1≤�,�≤10001≤n,m≤1000;
对于所有评测用例, 1≤�,�≤100000,0≤�<220,1≤��≤��≤�1≤n,m≤100000,0≤x<220,1≤li≤ri≤n, 0≤��<2200≤Ai<220 。
运行限制
- 最大运行时间:1s
- 最大运行内存: 512M
#include<bits/stdc++.h> using namespace std; const int maxn = 100000 + 10; int Left[maxn], pos[(1 << 20) + 10]; int a[maxn], n, m, x; int main() { cin >> n >> m >> x; for(int i = 1; i <= n; i++) { cin >> a[i]; Left[i] = pos[a[i] ^ x]; pos[a[i]] = i; } while(m--) { int l, r; cin >> l >> r; int t=0; for(int i=l;i<=r;i++) { if(Left[i]>t) t=Left[i]; } if(t>= l) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }
线段树查询
#include<bits/stdc++.h> using namespace std; const int maxn = 100000 + 10; int tree[maxn << 2]; int Left[maxn], pos[(1 << 20) + 10]; int a[maxn], n, m, x; //线段树模板 //1 1 n void build(int o, int l, int r) { if(l == r) { tree[o] = Left[l]; cout<<"tree["<<o<<"]"<<"=Left["<<l<<"]"<<endl; return; } int mid = (l + r) >> 1; build(o << 1, l, mid); cout<<"build("<<(o<<1)<<","<<l<<","<<mid<<")"<<endl; build(o << 1 | 1, mid + 1, r); cout<<"build("<<(o<<1|1)<<","<<mid+1<<","<<r<<")"<<endl; tree[o] = max(tree[o << 1], tree[o << 1 | 1]); cout<<"tree["<<o<<"]"<<"=max(tree["<<(o<<1)<<"],tree["<<(o<<1|1)<<"])"<<endl; } //查询区间[L,R]的最大值 //1 1 n l r int query(int o, int l, int r, int L, int R) { if(L <= l && r <= R)return tree[o]; int mid = (l + r) >> 1; int ans = 0; if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R)); if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));//找最大的left[idx] return ans; } int main() { cin >> n >> m >> x; for(int i = 1; i <= n; i++) //预处理Left数组 { cin >> a[i]; Left[i] = pos[a[i] ^ x]; pos[a[i]] = i; } build(1, 1, n);//线段树建树 while(m--) { int l, r; cin >> l >> r; if(query(1, 1, n, l, r) >= l)//查询区间最值 cout<<"yes"<<endl; else cout<<"no"<<endl; } cout<<"tree\n"; for(int i=0;i<=8;i++) { cout<<tree[i]<<" "; } return 0; }
标签:int,选数,pos,用例,异或,maxn,Left From: https://www.cnblogs.com/weinan030416/p/17066751.html