原文链接
莫队二次离线
最近学了这个黑科技，来写篇题解分享一下。
顺便(orz;lxl)
Part.1 问题引入
有一个序列，每次查询一个区间中有几个二元组的的异或值在二进制下有(k)个(1)。
考虑莫队。
先用莫队转化问题，先考虑我们已经求出([l,r])的答案，要将(r+1)加入答案，其他的转移类似，现在问题转化为求(r+1)与([l,r])中有几个数的异或值有(k)个(1)。
Part.2 暴力
考虑暴力怎么做，由于值域很小((a_ileq 16384))，我们可以先预处理出一个数组(x)中存储有哪些数在二进制数下有(k)个1，每一次插入一个数(a_i)，就把它与(x)数组中所有的数异或起来的值放进一个桶里，然后查询就直接查当前数在桶中出现了几次。为什么呢？
比如我们有(a_i;xor;a_j=x)，就有(a_i;xor;x=a_j)，我们已经将(a_i;xor;x)放入桶里，直接查就可以了。
但这样有个问题，莫队有(nsqrt n)次转移，每次修改时如果真的暴力插入桶的话，复杂度就是(O(nsqrt n imes x))（设(x)为数组中的元素个数），显然是不对的，考虑进一步优化。
Part.3 解决
我们进一步挖掘性质，发现我们要求的是(r+1)对([l,r])的贡献，实际上我们可以先求它对([1,r])的贡献，再减去([1,l-1])的贡献，为什么要这么做呢？我们可以发现(r+1)对前者的贡献是可以(O(n imes x))是可以预处理的，就只用考虑后者的贡献了。
如下图，我们考虑我们已经算出了红色部分的贡献了。
然后我们需要转移绿色部分的贡献。
这个过程中我们可以发现，左端点是不变，即我们的([1,l-1])的答案是不变的，即不用修改，也就是说，我们只有查询操作，而查询操作时(O(1))的！
所以我们二次离线，先跑一次莫队，将如上的绿色区间保存下来，再统一处理。
具体实现可以每个点开一个(vector)，然后移动右端点的时，我们将如上的绿色区间保存在左端点，移动左端点时，将绿色区间保存在右端点。
然后我们把这些(vector)扫一遍，修改就只有在从(i)到(i+1)时才有，查询还是(O(nsqrt n))次，但单次是(O(1))的。
所以我们的总复杂的就变成了(O(nsqrt n+n imes x))！
总结一下，对于那种查询复杂度很高的东西，并且同时询问信息还可以差分的问题，我们就可以用莫队二次离线解决。
做完这题可以去做一下这个，稍微要复杂一点，需要一些其他的数据结构辅助。
这个算法理解其实并不难，主要是代码细节比较多，建议尽量先自己实现，遇到问题再看题解的代码。
struct Query_Node
{
int l,r,id,kl;
ll ans;
bool operator < (const Query_Node &u) const{
return kl!=u.kl?kl<u.kl:(kl&1?r<u.r:r>u.r);
}
}q[maxn];
struct Node
{
int l,r,id;
Node(int l=0,int r=0,int id=0) : l(l),r(r),id(id) {}
};
ll ans[maxn];
vector<Node> two[maxn];
int n,m,k,a[maxn],tax[maxn],klen,pre[maxn];
int isu[maxn],ist;
inline int calc(int x)
{
int ans=0;
while(x) ++ans,x-=(x&(-x));
return ans;
}
template<typename T>
inline void read(T &x)
{
char c;int f=1;
while(!isdigit(c=getchar())) (c=='-')&&(f=-1);
x=c^48;
while(isdigit(c=getchar())) x=x*10+(c^48);
x*=f;
}
int main()
{
read(n);read(m);read(k);
for(int i=1;i<=n;++i)
read(a[i]);
klen=n/sqrt(m*2/3);
for(int i=1;i<=m;++i)
{
read(q[i].l);read(q[i].r);q[i].id=i;
q[i].kl=(q[i].l-1)/klen+1;
}
sort(q+1,q+m+1);
for(int i=0;i<=maxa;++i) if(calc(i)==k) isu[++ist]=i;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=ist;++j) ++tax[isu[j]^a[i]];
pre[i]=tax[a[i+1]];
}
for(int i=1,l=1,r=0;i<=m;++i)//先空跑莫队，找出绿色区间，同时处理前者的贡献
{
if(l<q[i].l) two[r].push_back(Node(l,q[i].l-1,-i));
while(l<q[i].l) q[i].ans+=pre[l-1],++l;
if(l>q[i].l) two[r].push_back(Node(q[i].l,l-1,i));
while(l>q[i].l) q[i].ans-=pre[l-2],--l;
if(r<q[i].r) two[l-1].push_back(Node(r+1,q[i].r,-i));
while(r<q[i].r) q[i].ans+=pre[r],++r;
if(r>q[i].r) two[l-1].push_back(Node(q[i].r+1,r,i));
while(r>q[i].r) q[i].ans-=pre[r-1],--r;
}
memset(tax,0,sizeof(tax));
//二次离线，处理后者的贡献
for(int i=1;i<=n;++i)
{
for(int j=1;j<=ist;++j) ++tax[isu[j]^a[i]];
for(vector<Node>::iterator it=two[i].begin();it!=two[i].end();++it)
for(int j=it->l;j<=it->r;++j)
{
int tmp=tax[a[j]];
if(j<=i&&k==0) tmp--;
if(it->id<0) q[-it->id].ans-=tmp;
else q[it->id].ans+=tmp;
}
}
for(int i=1;i<=m;++i) q[i].ans+=q[i-1].ans,ans[q[i].id]=q[i].ans;
for(int i=1;i<=m;++i)
printf("%lld
",ans[i]);
return 0;
}