题意
给定一个长度为 \(n\) 的序列和一个常数 \(k\)，每次询问一个区间 \([l,r]\) 内，有多少对 \(i,j\)，满足 \(l\leq i<j \leq r\) ，且 \(a_i \oplus a_j\) 的二进制表示下恰好有 \(k\) 位为 \(1\)。
数据范围
\(1 \leq n,m \leq 10^5,0 \leq a_i <2^{14},0\leq k\leq 14\)。
思路
按照普通莫队的思路，设当前的指针为 \(L,R\)，询问的区间为 \(l,r\)，\(S_{x,y}\) 表示 \(1 \sim x\) 中有多少数与 \(a_y\) 配对。以 \(R\) 转移到 \(R+1\) 为例，更新的答案就为 \(S_{R,R+1}-S_{L-1,R+1}\) 。对于形如 \(S_{x,x+1}\) ，可以直接预处理（后面会提到），但是对于 \(S_{R,L-1}\) 这类问题，直接预处理的代价太大，于是就可以考虑二次离线处理。
首先考虑预处理 \(S_{x,x+1}\)。记 \(f[i]\) 表示 \(1\sim i\) 中有多少数与 \(a[i+1]\) 配对，\(w[i][x]\) 表示 \(1\sim i\) 中有多少数与 \(x\) 配对。显然，有 \(f[i]=w[i][a[i+1]]\)。
对于等式 \(a \oplus b=y\)，两边同时异或 \(b\)，由于 \(b \oplus b=0,a \oplus 0=a\)，得到 \(a=b \oplus y\)，而 \(y\) 就是所有满足二进制下有 \(k\) 位为 \(1\) 的数。由于 \(a\oplus b <2^{14}\)，所以 \(y\) 一共有 \(C_{14}^{k}\) 个，也就是最多只有 \(3432\) 个。
考虑从 \(1 \sim n\) 枚举 \(a_i\)，再枚举所有的 \(y\)，令 \(g[i][a_i \oplus y]++\)，由于 \(g[i+1][x]\) 和 \(g[i][x]\) 只存在 \(a[i+1]\) 的差别，可以直接略去第一维。此时，\(g[x]\) 就表示 \(1\sim i\) 中有多少数与 \(x\) 配对，那么就可以直接更新 \(f[i]=g[a[i+1]]\)。至此预处理完毕，时间复杂度为 \(O(C_{14}^{k}n)\)。
莫队转移时，分为四类讨论需要二次离线的询问。
\(1.\)从 \(R\) 转移到 \(r\) 。总增加的贡献为 \(\sum_{i=R}^{r-1} S_{i,i+1}-S_{L-1,i+1}\)。前面一部分直接用 \(\sum_{i=R}^{r-1} f[i]\) 转移即可。后面一部分则记录到 \(L-1\) 的询问中二次离线处理。
\(2.\)从 \(r\) 转移到 \(R\)。思路同上，但是需要注意此时是减去贡献，所以需要改变一下符号，具体实现可以看代码。
3.从 \(L\) 转移到 \(l\)。总增加的贡献为 \(\sum_{i=l}^{L-1} S_{R,i}-S_{i,i}\)。此时需要注意，尽管 \(i=i\) 的情况在题意中是不合法的，但是此时仍然需要特判 \(k=0\) 的情况，因为尽管 \(f[i]\) 中不包含异或自己的情况，但是后面会提到，在二次离线是是会把这类情况算进去的。
4.从 \(l\) 转移到 \(L\)。思路同上，也别忘了变符号。
下面讨论二次离线的写法。
对于每一个 \(i\)，设前面莫队的时候需要加上一个 \(p*\sum_{j=l}^{r}S_{i,j}\) （其中 \(|p|=1\)，表示整体的正负符号）。此时 \(j\) 和 \(i\) 的大小关系就是不确定的，也就是上面提到为什么要特判 \(k=0\) 的情况。此时注意到区间 \(1 \sim i\) 是固定的，那么按照预处理时的方式，在解决询问时就可以得到所有 \(S_{i,j}\) 的值（具体实现可以参考代码）。此时直接枚举 \(j\) 更新答案，根据莫队的性质，每次询问的区间 \([l,r]\) 就是在离线莫队时相邻两个询问在一个方向（左边或右边）相差的范围，总的更新次数不会超过 \(O(n\sqrt m)\)。至此就得到了一个复杂度为 \(O(C_{14}^{k}n+n\sqrt m)\) 的算法。
最后，需要注意一下，在莫队时记录的答案只是与上一个区间的差值，相当于差分数组，所以还需要做一次前缀和。同时，答案别忘了开** long long**。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
#define LL long long
int g[N],f[N],len,n,m,num[N],k,tot,a[N]; LL ans[N],res[N];
struct node{int l,r,id;}q[N];
struct twice{int id,l,r,sign;};
vector<twice>range[N];
bool cmp(node x,node y)
{
int i=x.l/len,j=y.l/len; return i!=j?i<j: x.r<y.r;
}
int count(int x){int res=0; for(int i=0;i<14;i++) res+=(x>>i)&1;return res;}
int main()
{
scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++) scanf("%d",&a[i]);len=sqrt(n);
for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;sort(q+1,q+m+1,cmp);
for(int i=0;i<(1<<14);i++) if(count(i)==k) num[++tot]=i;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=tot;j++) ++g[a[i]^num[j]];
f[i]=g[a[i+1]];
}
for(int i=1,L=1,R=0;i<=m;i++)
{
int l=q[i].l,r=q[i].r;
if(R<r) range[L-1].push_back(twice{i,R+1,r,-1});
while(R<r) res[i]+=f[R++];
if(R>r) range[L-1].push_back(twice{i,r+1,R,1});
while(R>r) res[i]-=f[--R];
if(L<l) range[R].push_back(twice{i,L,l-1,-1});
while(L<l) res[i]+=f[L-1]+(!k),L++;
if(L>l) range[R].push_back(twice{i,l,L-1,1});
while(L>l) res[i]-=f[L-2]+(!k),L--;
}
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=tot;j++) ++g[a[i]^num[j]];
for(int j=0;j<range[i].size();j++)
for(int k=range[i][j].l;k<=range[i][j].r;k++)
res[range[i][j].id]+=g[a[k]]*range[i][j].sign;
}
for(int i=2;i<=n;i++) res[i]+=res[i-1];
for(int i=1;i<=n;i++) ans[q[i].id]=res[i];
for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
return 0;
}