Description
给定一个长度为 (n) 的子序列 (a),再给定一个数字 (k),给出 (m) 组询问,每组询问给出一个区间,问有多少区间的异或和为 (k)。
Solution
求一个区间的异或和,本质上就是求前缀和序列中两个数的异或,当然这两个点不能重合
于是考虑莫队,下面只讨论前缀和序列,用桶维护区间中的所有数,添加或删除时顺便记录一下答案即可
注意我们在维护答案时,要保证选择的是无序对
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define bel(x) (x/sq)
const int N = 2000005;
int n,m,k,a[N],out[N],sq;
namespace mo
{
int a[N],n,m,ind,c[N];
struct range
{
int l,r,id;
bool operator < (const range &b)
{
if(bel(b.l)==bel(l)) return r<b.r;
return l<b.l;
}
} b[N];
void insert(int l,int r)
{
++ind;
b[ind]={l,r+1,ind};
}
void init(int _n,int _m,int *src)
{
n=_n+1;
m=_m;
for(int i=1;i<n;i++) a[i+1]=src[i];
for(int i=1;i<=n;i++) a[i]^=a[i-1];
}
int l=1,r=0,ans;
void add(int i)
{
ans+=c[a[i]^k];
c[a[i]]++;
}
void dec(int i)
{
c[a[i]]--;
ans-=c[a[i]^k];
}
void adjust(int ql,int qr)
{
while(r<qr) add(++r);
while(l>ql) add(--l);
while(r>qr) dec(r--);
while(l<ql) dec(l++);
}
void solve()
{
sort(b+1,b+m+1);
for(int i=1;i<=m;i++)
{
adjust(b[i].l,b[i].r);
out[b[i].id]=ans;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>k;
sq=sqrt(n)+1;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++)
{
int t1,t2;
cin>>t1>>t2;
mo::insert(t1,t2);
}
mo::init(n,m,a);
mo::solve();
for(int i=1;i<=m;i++) cout<<out[i]<<endl;
}