首页 > 代码库 > （莫队算法）CodeForces - 617E XOR and Favorite Number
（莫队算法）CodeForces - 617E XOR and Favorite Number
题意：
长度为n的数列，m次询问，还有一个k。每次询问询问询问从数列的L到R内有多少个连续子序列异或起来等于k。
分析：
因为事先知道这题可以用莫队写，就正好用这题练习莫队。
预处理每个前缀异或和。
然后莫队按分块排序后，不断更新，用一个数组cnt[]记录当前L到R前缀和的数量。
R向右拉，新增的数量就是cnt[pre^k]，pre表示当前这个R位置的前缀异或和，然后更新一下cnt。
其他的也类似。
算是一个比较好的入门题。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 #include <map> 6 #include <vector> 7 #include <algorithm> 8 9 using namespace std;10 11 const int maxn = 1100010;12 const int bk = 400;13 int n, q, k;14 struct Query {15 int l, r, index;16 };17 18 Query query[maxn];19 20 bool cmp(Query a, Query b) {21 if(a.l / bk == b.l / bk)return a.r < b.r;22 else return a.l / bk < b.l / bk;23 }24 25 long long a[maxn];26 long long ans[maxn];27 long long cnt[maxn];28 long long pre[maxn];29 long long res = 0;30 31 void add(int x) {32 res += cnt[x ^ k];33 cnt[x]++;34 }35 36 void del(int x) {37 cnt[x]--;38 res -= cnt[x ^ k];39 }40 41 int main() {42 scanf("%d%d%d", &n, &q, &k);43 cnt[0] = 1;44 pre[0] = 0;45 for(int i = 1; i <= n; i++) {46 scanf("%lld", &a[i]);47 pre[i] = pre[i - 1] ^ a[i];48 }49 for(int i = 0; i < q; i++) {50 scanf("%d%d", &query[i].l, &query[i].r);51 query[i].index = i;52 }53 sort(query, query + q, cmp);54 int left = 1, right = 0;55 for(int i = 0; i < q; i++) {56 if(right < query[i].r) {57 for(int j = right + 1; j <= query[i].r; j++) {58 add(pre[j]);59 }60 } else {61 for(int j = right; j > query[i].r; j--) {62 del(pre[j]);63 }64 }65 right = query[i].r;66 if(left < query[i].l) {67 for(int j = left; j < query[i].l; j++) {68 del(pre[j - 1]);69 }70 71 } else {72 for(int j = left - 1; j >= query[i].l; j--) {73 add(pre[j - 1]);74 }75 }76 left = query[i].l;77 ans[query[i].index] = res;78 }79 for(int i = 0; i < q; i++) {80 printf("%lld\n", ans[i]);81 }82 83 84 return 0;85 }
（莫队算法）CodeForces - 617E XOR and Favorite Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。