问题描述
给定一个长度为 �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。
#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; //线段树模板 void build(int o, int l, int r) { if(l == r) { tree[o] = Left[l]; return; } int mid = (l + r) >> 1; build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); tree[o] = max(tree[o << 1], tree[o << 1 | 1]); } //查询区间[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)); 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; } return 0; }
标签:int,选数,pos,整数,异或,ans,区间 From: https://www.cnblogs.com/weinan030416/p/17059879.html