学习莫队是非常有必要的
众所周知，莫队是一种优越的暴力算法，当我们在 \(NOIP\) 等考试中数据结构不会打且问题是离线时，我们就可以：莫队，启动！
好，切入正题，我们现在来看看莫队是什么：
例题传送门
简要题意：给定一个长度为 \(n\) 的序列 \(a\)，然后再给一个数字 \(k\)，再给出 \(m\) 组询问，每组询问给出一个区间，求这个区间里面有多少个子区间的异或值为 \(k\)。
\(1 \le n,m \le 10 ^ 5\)，\(0 \le k,a_i \le 10^6\)，\(1 \le l_i \le r_i \le n\)。
首先，他不是莫队的板子，所以我们先不讲莫队，先讲一些针对这道题的一些 \(trick\)
- 我们首先考虑定义 \(sum_i=sum_{i-1}\oplus a_i\)，容易证明，子区间 \([l,r]\) 的异或值就变成了两个数的异或值： \(sum_r \oplus sum_{l-1}\)
然后，我们开始讲莫队：
-
首先，我们定义 \(cnt_i\) 表示区间\([l,r]\) 中 \(sum=i\) 的个数
-
其次，对于区间 \([l,r]\)，我们考虑已经知道该区间的答案 \(ans_{l,r}\)，以及所有的 \(cnt_i\)
-
考虑，区间 \([l,r+1]\) 的答案，易证：\(ans_{l,r+1}=ans_{l,r}+cnt_{sum_{r+1}\oplus k}\)，然后，\(cnt_{sum{r+1}}++\)
-
考虑，区间 \([l,r-1]\) 的答案，易证：\(ans_{l,r-1}=ans_{l,r}-cnt_{sum_r\oplus k}\)，然后，\(cnt_{sum_r}--\)
-
考虑，区间 \([l+1,r]\) 的答案，易证：\(ans_{l+1,r}=ans_{l,r}-cnt_{sum_l\oplus k}\)，然后，\(cnt_{sum_l}--\)
-
考虑，区间 \([l-1,r]\) 的答案，易证：\(ans_{l-1,r}=ans_{l,r}+cnt_{sum_{l-1}\oplus k}\)，然后，\(cnt_{sum{l-1}}++\)
-
我们发现，只要我们令 \(le=1,ri=0\)，然后让 \(le,ri\) 进行加减到达 \([l,r]\) 就可知道 这个区间 \([l,r]\) 的答案，因为修改是\(O(1)\)，但最坏是修改 \(n\) 次，所以是 \(O(n)\)。
-
有 \(q\) 个询问，所以时间复杂度是 \(O(nq)\)
-
修改的时间复杂度已经不能再降了，所以我们考虑在修改次数上动手脚，令修改次数尽可能少，这时候我们就要对询问的区间进行排序，这就是为什么莫队是离线的
-
考虑将一个 \(1-n\) 分块，分成 \(\sqrt n\) 个块，分别是 \(1\sim\sqrt n,\sqrt n+1\sim 2\sqrt n,...,(\sqrt n-1)\sqrt n\sim n\)（注意，\(\sqrt n\)不一定整数，所以只要接近就好了，即 \(\sqrt n\) 向下或向上取整）
-
我们进行排序，以 \(q.l\) 为第一关键字，但注意，并不是直接令 \(q_i.l<q_j.l\)，而是判断 \(q_i.l\) 和 \(q_j.l\) 是否在同一个块内，如果不是的话，才令 \(q_i.l<q_j.l\)。
-
然后以 \(q.r\) 为第二关键字，如果 \(q_i.l\) 和 \(q_j.l\) 在同一个块内，则令 \(q_i.r<q_j.r\)
-
这样有什么好处呢？我们考虑 \(l\) 的修改次数，对于每一次修改 \(l\) 移动不超过 \(\sqrt n\) 次（当 \(l\) 在不同块时，只有可能从上一个块到下一个块，所以总的移动次数不超过\(2n\)，很小，可以忽略），因为询问有 \(q\) 个，所以修改 \(l\) 的时间复杂度是 \(O(q\sqrt n)\)
-
再考虑 \(r\) 的修改次数，因为在 \(l\) 属于同一个块的时候，\(r\) 是递增的，所以 \(r\) 的修改次数不超过 \(n\)，又因为有 \(\sqrt n\) 个块，所以修改 \(r\) 的时间复杂度是 \(O(n \sqrt n)\)
-
总的时间复杂度就是 \(O((n+q)\sqrt n)\)
-
\(WC\)(一种比赛)，从平方级别变成了根号级别，厉不厉害你莫队，这就通过这道题了
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+50,M=1e6+50;
ll n,m,k,sq;
ll a[N],b[N];
struct jgt
{
ll l,r,id;
}q[N];
bool cmp(jgt t1,jgt t2)
{
return b[t1.l]==b[t2.l] ? t1.r<t2.r : t1.l<t2.l;
}
ll gs[M*2],now;
void add(ll wz)
{
now+=gs[a[wz]^k];
gs[a[wz]]++;
}
void del(ll wz)
{
gs[a[wz]]--;
now-=gs[a[wz]^k];
}
ll ans[N];
int main()
{
scanf("%lld %lld %lld",&n,&m,&k);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
a[i]^=a[i-1];
}
sq=sqrt(n);
for(ll i=0;i<=n;i++)
b[i]=i/sq+1;
for(ll i=1;i<=m;i++)
{
scanf("%lld %lld",&q[i].l,&q[i].r);
q[i].l--;
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
ll le=0,ri=0;
gs[0]=1;
for(ll i=1;i<=m;i++)
{
while(ri<q[i].r) add(++ri);
while(ri>q[i].r) del(ri--);
while(le<q[i].l) del(le++);
while(le>q[i].l) add(--le);
ans[q[i].id]=now;
}
for(ll i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}