题意原文地址：https://blog.****.net/chenzhenyu123456/article/details/50574169
题意：有n个数和m次查询，每次查询区间[l, r]问满足ai ^ ai+1 ^ ... ^ aj == k的(i, j) (l <= i <= j <= r)有多少对。
思路：离线做。首先预处理前缀异或和sum[]，那么ai ^ ... ^ aj == sum[i-1] ^ sum[j]。
这样对一次查询[l, r]的处理，可以从左到右扫一次，统计k ^ sum[i]出现的次数(l <= i <= r)。
假设已经处理到[L, R]，对下一次的[l, r]处理——
若L < l，显然多余，需要去掉[L, l-1]的部分，若L > l需要加上[l, L-1]的部分，反之不需要处理。
若R > r，..................[r+1, R]......，若R < r........[R+1, r]......，..............。
用莫队做即可。
#include <bits/stdc++.h>
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff;
LL pos[maxn], c[maxn], s[maxn], cnt[<<], sum[maxn], out_ans[maxn];
LL n, m, ans, k;
struct node
{
LL r, l, id, res;
}Node[maxn]; int cmp(node a, node b)
{
if(pos[a.l] == pos[b.l])
return a.r < b.r;
return a.l < b.l;
} int cmp_id(node a, node b)
{
return a.id < b.id;
} void add(int x)
{
ans += cnt[sum[x]^k]; // 右区间拓展时： 这样就保证了c[i]^k 是在前面出现过的 因为如果没有出现过 则cnt对应的值为0 左区间同理
cnt[sum[x]]++;
} void dec(int x)
{
cnt[sum[x]]--; //右区间缩小时： 防止c[i]^k 是后边的 左区间同理
ans -= cnt[sum[x]^k]; } int main()
{
scanf("%lld%lld%lld", &n, &m, &k);
for(int i=; i<=n; i++)
{
scanf("%lld", &c[i]);
sum[i] = sum[i-] ^ c[i];
}
int block = sqrt(n);
for(int i=; i<=n; i++)
pos[i] = (i-)/block + ;
for(int i=; i<=m; i++)
{
scanf("%lld%lld", &Node[i].l, &Node[i].r);
Node[i].id = i;
Node[i].l--; //预处理
}
sort(Node+, Node+m+, cmp);
cnt[] = ;
for(int i=, l=, r=; i<=m; i++)
{
for(; r < Node[i].r; ++r)
add(r+);
for(; r > Node[i].r; r--)
dec(r);
for(; l < Node[i].l; ++l)
dec(l);
for(; l > Node[i].l; --l)
add(l-); Node[i].res = ans;
}
sort(Node+, Node+m+, cmp_id); for(int i=; i<=m; i++)
printf("%I64d\n",Node[i].res); return ;
}