必要异或运算性质：
归零律：a⊕a=0
结合律: a⊕b⊕c=a⊕(b⊕c)=(a⊕b)⊕c
交换律：a⊕b=b⊕a
因此, a⊕b=x⟺a⊕b⊕x=0⟺a⊕x=b
因此对于一个数a， 与a配对的数可以直接计算得出， 即为a⊕x
递推优化
不妨将满足题意的两个数a, b简称为数对， a、b中较小的下标叫下界.
定义dp[i]为[1, i]区间中所有数对中的最大下界
如样例1 2 3 4, 只有2 3的异或为1.
对于区间[1, 2]它不包含数对{2， 3}所以dp[2]应该为一个无效值， 取0
对于区间[1, 3] [1, 4]， 都仅且包含数对{2, 3}, 所以dp[3] = dp[4] = 2
dp[r]的实际意义想必大家都看出来了， 就是当查询区间[l, r], 右边界为r时， 至少包含一个数对时的左边界最大值, 所以如果l小于等于这个左边界最大值， [l, r]区间内就至少有一个数对。
代码实现
用哈希表last[X]记录数值X最后一次出现时的位置下标， dp[i]的求法是： 若ai⊕x最后一次出现的下标要大于dp[i-1]， 则dp[i] = last[ai⊕x], 否则dp[i] = dp[i-1]
即
dp[i]=max(dp[i−1],last[ai⊕x])
时间复杂度: O(n+m)
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int dp[N], n, m, x;
int main() {
cin >> n >> m >> x;
unordered_map<int, int> last;
for(int i=1; i<=n; i++) {
int a; cin >> a;
dp[i] = max(dp[i-1], last[x ^ a]);
//这句应该放到后面， 否则当x=0时会不正确(当x等于0时dp[i] = i, 但是要选两个不同位置的数)
//更正于2023/01/01
last[a] = i;
}
while (m -- ) {
int l, r; cin >> l >> r;
cout << (dp[r] >= l ? "yes" : "no") << endl;
}
return 0;
}
拿到题还以为是trie树，没想到是dp，强的
trie数不方便处理询问
怎么我这显示你这评论是20天前的
21天前回复，6了
因为这是蓝桥杯的题😅😅
刚开始我也是这么想的，但是他要查询区间，不太好搞
我感觉要加上一条性质a⊕0=a
然后a⊕b=x⟺a⊕b⊕x=x⊕x⟺a⊕b⊕x=0⟺a⊕b⊕x⊕b=0⊕b=b
这样让人更好理解变换的过程😅
就需要你这个证明!
大佬我这里有个问题啊，请问这个选取两个数可以是相同位置的两个吗？如果不可以的话我认为last[a] = i; 放到dp[i] = max(dp[i-1], last[x ^ a]);之后会比较好？具体测试数据如下：
4 2 0
1 3 2 2
1 3
1 4
测试结果按照你的代码是yes yes，调换顺序后是no yes
确实应该放到后面， 测试里好像没有x=0的数据， 当时就没注意。
是的，y总这里没有卡这个数据
样例里面不是有一个 例子 取得两个数都是相同的
tql 蒟蒻给一组数据大家可以手动感受一下
x == 3 a[i] => 0 7 3 4 2 i => 1 2 3 4 5 a[i] => 7 0 3 4 2 i => 1 2 3 4 5看了题解 直接顿悟了 。讲的太好了
厉害的，一针见血的
orz orz
dp[i] > i 这种情况代表什么呀
学废了
tql
你是懂dp的
hh不清楚你说的是正话还是反话， 就我个人观点， DP和递推就是一个东西， DP题就是一个设计递推关系的过程。
是太强了hh 看过你的题解真的豁然开朗，最开始还想着能不能跟前缀和数组一样的处理方式预处理一下，根本没想到是dp的问题，膜拜膜拜
orz
orz
大家可以看一下我写的题解 https://blog.csdn.net/qq_73704268/article/details/145800906?sharetype=blogdetail&sharerId=145800906&sharerefer=PC&sharesource=qq_73704268&spm=1011.2480.3001.8118
想问下为什么last从unordered_map变成int数组就不正确呀
max里为啥要加个dp( i - 1)啊
dp[i-1]表示i-1之前的数存在异或的最大值，就是last求的不存在，但是之前存在i-1之前的可能存在一个比0大的值，所以要比较一下
就是i这个点的数不满足，但i之前的点有可能有满足条件的
太太太厉害啦！！！！又学到了 开心o(￣▽￣)ブ
有一点不理解，last中的a^x如果相同，取出来的下标是最大值的吗？
救救，你是怎么过的dp[1e5+10],我1e6都被卡，得1e7才行
unordered_map[HTML_REMOVED] last;不限大小好家伙牛
acwing评测器太慢了确实可能会被卡
%%%
若ai⊕xai⊕x最后一次出现的下标要大于dp[i-1], 为什么要大于呀