选数异或
给定一个长度为 $n$ 的数列 $A_1,A_2,\ldots,A_n$ 和一个非负整数 $x$，给定 $m$ 次查询，每次询问能否从某个区间 $[l,r]$ 中选择两个下标不同的数使得他们的异或等于 $x$。
输入格式
输入的第一行包含三个整数 $n,m,x$。
第二行包含 $n$ 个整数 $A_1,A_2,\ldots,A_n$。
接下来 $m$ 行，每行包含两个整数 $l_i,r_i$ 表示询问区间 $[l_i,r_i]$。
输出格式
对于每个询问，如果该区间内存在两个数的异或为 $x$ 则输出 yes ，否则输出 no 。
数据范围
对于 $20\%$ 的评测用例，$1 \leq n,m \leq 100$；
对于 $40\%$ 的评测用例，$1 \leq n,m \leq 1000$；
对于所有评测用例，$1 \leq n,m \leq 100000$，$0 \leq x < 2^{20}$，$1 \leq l_i \leq r_i \leq n$，$0 \leq A_i < 2^{20}$。
输入样例：
4 4 1 1 2 3 4 1 4 1 2 2 3 3 3
输出样例：
yes
no
yes
no
样例解释
显然整个数列中只有 $2,3$ 的异或为 $1$。
解题思路
对于一个询问区间$[l, r]$，我们要在这个区间找到两个数使得$a_i \wedge a_j = x$，其中$l \leq i < j \leq r$。因此容易想到可以枚举$j$，然后在前面找到一个满足条件的$i$，即$a_i = a_j \wedge a_j$，因此在枚举的过程中可以开个哈希表来记录枚举过的数，这种做法的时间复杂度为$O(n \cdot m)$。
或者换一个方法，可以预处理出来每一个数$a_i$左边离它最近的与它匹配的数的下标，如果这个下标在区间$[l, r]$中那么在这个区间中一定存在一组解。定义$f(i)$表示在$a_i$左边与$a_i$配对的最近的一个数的下标，因此如果$a_i$和$a_{f(i)}$是满足条件的一个数对，那么应该有$l \leq f(i) < i \leq r$。因此问题就等价于是否存在一个$i$，$l \leq i \leq r$，使得$l \leq f(i) \leq r$。这种做法的时间复杂度还是$O(n \cdot m)$，因此还需要看看是否存在其他性质。如果在小于$l$的位置中取一个$i$，可以发现这个$i$对应的$f(i)$不可能在区间$[l, r]$范围内，因为$f(i) < i < l$。因此我们可以把$i$的范围扩大到$1 \leq i \leq r$，问题可以变成在$1 \leq i \leq r$是否存在$i$使得$l \leq f(i) \leq r$，进一步，因为$f(i) < i \leq r$，因此就变成能否使得$f(i) \geq l$。因此我们可以求出$f(i)$后（从左往右遍历的过程中开个哈希表记录每个数最新出现的下标），再预处理$g(i) = \max\limits_{1 \leq j \leq i}{f(j)}$，如果有$g(i) \geq l$，那么意味着在以$i$为右端点的前缀中存在一个$f(i) \geq l$。
AC代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 1e5 + 10, M = (1 << 20) + 10; 5 6 int mp[M], g[N]; 7 8 int main() { 9 int n, m, x; 10 scanf("%d %d %d", &n, &m, &x); 11 for (int i = 1; i <= n; i++) { 12 int v; 13 scanf("%d", &v); 14 g[i] = max(g[i - 1], mp[v ^ x]); 15 mp[v] = i; 16 } 17 while (m--) { 18 int l, r; 19 scanf("%d %d", &l, &r); 20 printf("%s\n", g[r] >= l ? "yes" : "no"); 21 } 22 23 return 0; 24 }
再给出我一开始的做法，比较的麻烦。
和上一种做法一开始的思路一样，只不过这里是枚举每个满足条件的数对左边的那个数（上一种做法是枚举右边的数）。假设能与$a_i$配对的数是$a_j$，有$j > i$，可以发现当$j$越小，那么$[i, j]$能够被更多的询问区间所完全覆盖，这是因为如果有$a_{j'} = a_{j}$且$j' > j$，并且$[i, j'] \in [l, r]$，那么也一定会有$[i, j] \in [l, r]$，因此区间$[i, j]$的长度越小越好。所以可以一开始把所有的查询区间记录下来（离线处理），然后枚举$i$，找到$a_j$后就有区间$[i, j]$，然后枚举所有的询问区间，把完全覆盖$[i, j]$的都标记成$\text{yes}$，时间复杂度还是$O(n \cdot m)$。可以发现如果对于每个$i$都枚举所有的询问区间，很明显会有冗余，比如对于某个$i$，枚举$l > i$的询问区间是没有意义的，因此我们可以对询问区间按照左端点从小到大排序，每次枚举到到$i$时，把$l \leq i$的询问区间加入到优先队列中，然后这个优先队列是根据区间的右端点来维护一个大根堆，因此每次弹出堆顶元素，如果$r \geq j$，那么这个区间就被标记成$\text{yes}$，同时把这个区间弹出优先队列，时间复杂度是$O(n \log{m})$。
AC代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef pair<int, int> PII; 5 6 const int N = 1e5 + 10, M = 1 << 20; 7 8 int a[N]; 9 int l[N], r[N]; 10 int p[N]; 11 vector<int> mp[M]; 12 string ans[N]; 13 14 int main() { 15 int n, m, x; 16 scanf("%d %d %d", &n, &m, &x); 17 for (int i = 1; i <= n; i++) { 18 scanf("%d", a + i); 19 } 20 for (int i = 0; i < m; i++) { 21 scanf("%d %d", l + i, r + i); 22 p[i] = i; 23 ans[i] = "no"; 24 } 25 sort(p, p + m, [&](int a, int b) { // 根据询问区间的左端点升序排序 26 return l[a] < l[b]; 27 }); 28 for (int i = 1; i <= n; i++) { 29 mp[a[i]].push_back(i); // 哈希表记录每个数所对应的所有下标 30 } 31 priority_queue<PII> pq; 32 for (int i = 1, j = 0; i <= n; i++) { 33 while (j < m && l[p[j]] <= i) { // 把左端点不超过i的区间加入优先队列 34 pq.push({r[p[j]], p[j]}); 35 j++; 36 } 37 int t = a[i] ^ x; 38 auto it = upper_bound(mp[t].begin(), mp[t].end(), i); // 在满足a[i]^a[j]=x的j中找到大于i最小的j 39 if (it != mp[t].end()) { // 存在与a[i]对应的a[j] 40 while (!pq.empty() && pq.top().first >= *it) { // 把区间右端点大于等于j的区间标记成yes并弹出队列 41 ans[pq.top().second] = "yes"; 42 pq.pop(); 43 } 44 } 45 } 46 for (int i = 0; i < m; i++) { 47 printf("%s\n", ans[i].c_str()); 48 } 49 50 return 0; 51 }
参考资料
AcWing 4645. 选数异或（寒假每日一题2023）：https://www.acwing.com/video/4586/
原文链接: https://www.cnblogs.com/onlyblues/p/17036545.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/310902
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
