洛谷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;
}
