洛谷P4462 [CQOI2018] 异或序列 题解
题意：
已知一个长度为 $n$ 的整数数列 $a_1,a_2,\dots,a_n$，给定查询参数 $l,r$，问在 $a_l,a_{l+1},\dots,a_r$ 区间内，有多少子区间满足异或和等于 $k$。也就是说，对于所有的 $x,y (l \leq x \leq y \leq r)$，能够满足 $a_x \bigoplus a_{x+1} \bigoplus \dots \bigoplus a_y = k$ 的 $x,y$ 有多少组。
输入格式：
输入文件第一行，为 $3$ 个整数 $n,m,k$。
第二行为空格分开的 $n$ 个整数，即 $a_1,a_2,..a_n$。
接下来 $m$ 行，每行两个整数 $l_j,r_j$，表示一次查询。
输出格式：
输出文件共 $m$ 行，对应每个查询的计算结果。
数据范围：
对于 $30\%$ 的数据，$1 \leq n, m \leq 1000$。
对于 $100\%$ 的数据，$1 \leq n, m \leq 10^5$，$0 \leq k, a_i \leq 10^5$，$1 \leq l_j \leq r_j \leq n$。
发现我连莫队的板子都没有，赶紧补一补。关键词：莫队 模板
区间异或和可以用前缀和预处理一下，题目就变成了 $[l - 1,r]$ 内存在多少个二元组 $(x,y)$ 满足 $x\oplus y = k$ 。
然后我们来讲这道题怎么用莫队做，以及莫队是啥。
莫队是一种离线+分块的暴力算法，大概的感觉就是两个小手🖐️在询问间跳来跳去。
莫队的使用非常广泛甚至可以扯到组合计数题（反正我不会），比如今天集训的防AK题（反正听不懂）
例如一个询问 $[3,5]$ 和另一个询问 $[1,4]$ ，我们先暴力把 $[3,5]$ 的答案算出来。
那么怎么算 $[1,4]$ 呢？此时两个小手🖐️ $l,r$ 分别在 $3,5$ 上，我们把他们跳到 $1,4$ 上。
具体地，$l$ 从 $3$ 暴力移到 $1$ ，然后把答案算进去，此时两个小手🖐️ $l,r$ 分别在 $1,5$ 上，并且我们有 $[1,5]$ 的答案了
然后我们把 $r$ 从 $5$ 暴力移到 $4$ ，并把原来计算的贡献删掉。最后两个小手🖐️ $l,r$ 就分别在 $1,4$ 啦！
那么问题来了，这跟暴力有啥区别？哎，都用分块了，这能叫暴力吗。
不妨记块长为 $B$ ，我们按照以下规则对询问 $q_i$ 进行排序：
- 询问 $l$ 所处的块相同时，按 $r$ 递增排序。
- 询问 $l$ 所处的块不同时，按所处块的编号 $\mathtt{bl}$ 递增排序。
然后我们来分析一下复杂度（认为 $n,m$ 同阶）。
- 在同一个块内，右端点移动不超过 $\mathcal{O}(n)$ ，有 $\mathcal{O}(\frac{n}{B})$ 个块，这部分复杂度为 $\mathcal{O}(\frac{n^2}{B})$
- 在块间转移时，右端点移动不超过 $\mathcal{O}(n)$ ，有 $\mathcal{O}(\frac{n}{B})$ 个块，这部分复杂度为 $\mathcal{O}(\frac{n^2}{B})$
- 在同一个块内，左端点移动不超过 $\mathcal{O}(B^2)$ ，有 $\mathcal{O}(\frac{n}{B})$ 个块，这部分复杂度为 $\mathcal{O}(nB)$
- 在块间转移时，左端点移动不超过 $\mathcal{O}(2B)$ ，有 $\mathcal{O}(\frac{n}{B})$ 个块，这部分复杂度为 $\mathcal{O}(n)$
因此总复杂度为 $\mathcal{O}(nB+\frac{n^2}{B})$ ，$B$ 取 $\sqrt{n}$ 时复杂度为 $\mathcal{O}(n\sqrt{n})$ 最优。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
int n,m,k,B,res,a[N],ans[N],o[N * 2]; // o[i]表示当前区间有多少个数异或和为i
struct node { int l,r,id,bl; } q[N];
bool cmp(node x, node y) {
return x.bl == y.bl ? x.r < y.r : x.bl < y.bl;
}
void add(int x) { res += o[x ^ k]; ++o[x]; }
void del(int x) { --o[x]; res -= o[x ^ k]; }
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m >> k; B = sqrt(n);
for(int i = 1; i <= n; i++) { cin >> a[i]; a[i] ^= a[i - 1]; }
for(int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r; --q[i].l; // 本题中是前缀和，因此要把 l 减去 1
q[i].id = i; q[i].bl = (q[i].l - 1) / B + 1;
}
sort(q + 1, q + 1 + m, cmp); int l = 1, r = 0;
for(int i = 1; i <= m; i++)
{
// 莫队的删除一定要在添加之后！！！否则在一些题目会出现计数为负数的情况！！
while(l > q[i].l) add(a[--l]);
while(r < q[i].r) add(a[++r]);
while(l < q[i].l) del(a[l++]);
while(r > q[i].r) del(a[r--]);
ans[q[i].id] = res;
}
for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
return 0;
}
