题意:
分析:
板子题,没什么思维难度,但坑很多
tip:
- 和普通莫队不一样,异或时需要考虑 \(l-1\) 位置的前缀异或值
- 异或可能会使值变大,所以桶需要开到值域的 2 倍左右
代码:
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
#define inl inline
#define reg register
using namespace std;
namespace zzc
{
typedef long long ll;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const ll maxn = 1e5+5;
const ll maxm = 4e6+5;
const ll blo = 350;
ll n,cnt=1,qt,k,num;
ll bel[maxn],a[maxn],pre[maxn],ans[maxn],t[maxm];
struct que
{
ll l,r,id;
bool operator <(const que &b)const
{
return bel[l]==bel[b.l]?r<b.r:l<b.l;
}
}q[maxn];
void add(int x)
{
int tmp=pre[x]^k;
num+=t[tmp];
t[pre[x]]++;
}
void del(int x)
{
int tmp=pre[x]^k;
t[pre[x]]--;
num-=t[tmp];
}
void work()
{
n=read();qt=read();k=read();
for(reg int i=1;i<=n;i++)
{
a[i]=read();pre[i]=pre[i-1]^a[i];
if(i%blo==0) cnt++;
bel[i]=cnt;
}
for(reg int i=1;i<=qt;i++)
{
q[i].l=read()-1;
q[i].r=read();
q[i].id=i;
}
sort(q+1,q+qt+1);
int l=1,r=0;
for(reg int i=1;i<=qt;i++)
{
while(q[i].l<l) add(--l);
while(q[i].r>r) add(++r);
while(q[i].l>l) del(l++);
while(q[i].r<r) del(r--);
ans[q[i].id]=num;
}
for(reg int i=1;i<=qt;i++) printf("%lld ",ans[i]);
}
}
int main()
{
zzc::work();
return 0;
}