如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
前言
众所周知，莫队是一种可爱的离线算法，它的时间复杂度为 $O(n\sqrt m\,f(x))$，$f(x)$ 为挪指针时更新答案复杂度，当 $f(x)=O(1)$ 时，我们可以接受，但 $f(x)=O(\log n)$ 甚至更大时，我们可能就无法接受了，而 莫队二次离线 可以让复杂度降到我们能接受的范围内——$O(n\sqrt m+n\,f(x))$。
适用范围：
- 一个数对区间的贡献与区间内的数有关；
- 设 $F(x,[l,r])$ 为 $x$ 对区间 $[l,r]$ 的贡献，其满足性质 $F(x,[l,r])=F(x,[1,r])-F(x,[1,l-1])$。
实现
考虑在挪指针时对答案产生了哪些贡献，下文的 $f(x,l,r)$ 表示 $a_x$ 对 $[l,r]$ 的贡献，$F(x,l)=f(x,1,l)$。
在右指针移动到 $x$ 时，会产生的答案变动为 $f(x,l,x-1)=F(x,x-1)-F(x,l-1)$ ；
在左指针移动到 $x$ 时，会产生的答案变动为 $f(x,x+1,r)=F(x,r)-F(x,x)$。
我们注意到，$F(x,x-1)$，$-F(x,x)$ 是可以预处理的，莫队时直接 $O(1)$ 修改答案即可，而且一般情况下 $F(x,x-1)=F(x,x)$，毕竟一个数一般不会对自己有贡献，可以偷个懒。
莫队的指针移动是连续的，也就是说，在上面式子中的 $-F(x,l-1)$ 和 $F(x,r)$ 部分单独计算实际上是形如 $-F(a,l-1)-F(a+1,l-1)-F(a+2,l-1)-\cdots-F(k,l-1)$ 和 $F(a,r)+F(a-1,r)+F(a-2,r)+\cdots+F(k,r)$ 的，那么我们可以使用五元组 $(a,k,l-1,-1,i)$ 和 $(a,k,r,1,i)$ 将这些移动产生的贡献存下来，$i$ 表示该移动在哪个询问期间发生，在莫队结束后使用扫描线处理，不懂没关系，看下代码（养成好习惯，两个指针的移动顺序不要写错）：
for(int i=1,l=1,r=0;i<=m;i++){
if(l>q[i].l) v[r].emplace_back(q[i].l,l-1,i,1);
while(l>q[i].l) --l,q[i].ans-=p[l];
if(r<q[i].r) v[l-1].emplace_back(r+1,q[i].r,i,-1);
while(r<q[i].r) ++r,q[i].ans+=p[r];
if(l<q[i].l) v[r].emplace_back(l,q[i].l-1,i,-1);
while(l<q[i].l) q[i].ans+=p[l],++l;
if(r>q[i].r) v[l-1].emplace_back(q[i].r+1,r,i,1);
while(r>q[i].r) q[i].ans-=p[r],--r;
}
这样还有最后一个问题，我们会发现一个指针在询问 $i$ 处的移动会对询问 $[i,m]$ 产生贡献，也就是说，我们得到的答案其实是差分的形式，需要求前缀和才能得到真正的答案。
代码
这里给出 P4887 的代码：
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<tuple>
int n,m,k,bel[100010],sz,a[100010],t[100010],p[100010];
struct query{
int l,r,id;
long long ans;
bool operator <(query const &x)const{
return bel[l]==bel[x.l]?r<x.r:l<x.l;
}
}q[100010];
std::vector<int> b;
std::vector<std::tuple<int,int,int,int>>v[100010];
long long ans[100010];
int bitcount(unsigned x){
int ans(0);
while(x)x-=x&-x,++ans;
return ans;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
if(k>14){
for(int i=1;i<=m;i++)puts("0");
return 0;
}
sz=n/sqrt(m);//莫队的正确块长，比sqrt(n)要快很多
for(int i=1;i<=n;i++)scanf("%d",a+i),bel[i]=(i-1)/sz+1;
for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
for(int i=0;i<16384;i++)
if(bitcount(i)==k)
b.push_back(i);
std::sort(q+1,q+m+1);
for(int i=1;i<=n;i++){//预处理
p[i]=t[a[i]];
for(const auto& x:b)++t[a[i]^x];
}
memset(t,0,sizeof(t));
for(int i=1,l=1,r=0;i<=m;i++){//莫队
if(l>q[i].l) v[r].emplace_back(q[i].l,l-1,i,1);
while(l>q[i].l) --l,q[i].ans-=p[l];
if(r<q[i].r) v[l-1].emplace_back(r+1,q[i].r,i,-1);
while(r<q[i].r) ++r,q[i].ans+=p[r];
if(l<q[i].l) v[r].emplace_back(l,q[i].l-1,i,-1);
while(l<q[i].l) q[i].ans+=p[l],++l;
if(r>q[i].r) v[l-1].emplace_back(q[i].r+1,r,i,1);
while(r>q[i].r) q[i].ans-=p[r],--r;
}
for(int i=1;i<=n;i++){//扫描线
for(const auto& x:b)++t[a[i]^x];
for(const auto& x:v[i]){
for(int j=std::get<0>(x);j<=std::get<1>(x);j++){
if(j<=i&&k==0) q[std::get<2>(x)].ans+=std::get<3>(x)*(t[a[j]]-1);
else q[std::get<2>(x)].ans+=std::get<3>(x)*t[a[j]];
}
}
}
for(int i=1;i<=m;i++)q[i].ans+=q[i-1].ans;//前缀和
for(int i=1;i<=m;i++)ans[q[i].id]=q[i].ans;
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}