5301: [Cqoi2018]异或序列

本文主要是介绍5301: [Cqoi2018]异或序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

看完题，容易想到把求一段区间改成求 前r的异或和 ^ 前l-1的异或和 等于k，
那么这个东西发现可以直接用莫队统计，没了.
c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y ; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y ; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{char c;int sign = 1;x = 0;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int N = 1e5+850;
int n,m,k,a[N];
int num[N],ans[N],belong[N];
struct DATA
{int l,r,id;
}q[N];const bool cmp(DATA a,DATA b) { return belong[a.l] < belong[b.l] || belong[a.l] == belong[b.l] && belong[a.r] < belong[b.r]; }int main()
{read(n); read(m); read(k);rep(i,1,n) read(a[i]);rep(i,2,n) a[i] = a[i]^a[i-1];rep(i,1,m) read(q[i].l), read(q[i].r),q[i].id = i;int d = max(1,(int)pow(n,2.0/3));rep(i,1,n) belong[i] = i/d;sort(q + 1,q + 1 + m,cmp);int r = 0,l = 1,now = 0;rep(i,1,m){--q[i].l;while(l < q[i].l){--num[a[l]];now -= num[a[l++]^k];}while(l > q[i].l){now += num[a[--l]^k];++num[a[l]];}while(r < q[i].r){now += num[a[++r]^k];++num[a[r]];}while(r > q[i].r){--num[a[r]];now -= num[a[r--]^k];}ans[q[i].id] = now;}rep(i,1,m) printf("%d\n",ans[i]);return 0;
}

这篇关于5301: [Cqoi2018]异或序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---