acwing选数异或 dp

题目链接：https://www.acwing.com/problem/content/description/4648/

题解链接[转载]：https://www.acwing.com/solution/content/137064/

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<vector>
 4 #include<string>
 5 #include<queue> 
 6 #include<map>
 7 #include<set>
 8 #define ll long long
 9 #define pii pair<int, int>
10 using namespace std;
11 const int N = 1E5 + 10;
12 const ll INF = INT64_MAX;
13 using namespace std;
14 
15 int n, m, x, a[N], dp[N];
16 map<int, int> mp;
17 
18 int main()
19 {
20     ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
21     cin >> n >> m >> x;
22     for(int i = 1 ; i <= n ; i++) {
23         cin >> a[i];
24     }
25     for(int i = 1 ; i <= n ; i++) {
26         dp[i] = max(dp[i - 1], mp[a[i] ^ x]);
27         mp[a[i]] = max(mp[a[i]], i); // mp[x]表示与x匹配的最右侧编号 
28     }
29     for(int i = 1 ; i <= m ; i++) {
30         int l, r;
31         cin >> l >> r;
32         if(dp[r] >= l) {
33             cout << "yes" << endl;
34         }else {
35             cout << "no" << endl;
36         }
37     }
38     
39     return 0;
40 }
41 /*
42     acwing 4648
43 */