莫队二次离线，是由数据结构题之神lxl所发明的一种数据结构。因为莫队中 \(ans\) 的变化同样不要求立刻反应，所以我们可以离线求解莫队中每次 \(ans\) 修改值 \(F(x,[l,r])\)。设单次求解修改值的时间复杂度为 \(O(k)\)，那么莫队二次离线可以将时间复杂度从 \(O(nk\sqrt n)\) 变为 \(O(n\sqrt n+nk)\)。
注：上文、下文的 \(F(x,[l,r])\) 表示区间 \([l,r]\) 对 \(ans_x\) 的贡献，\(f(x,a)=F(x,[1,a])\)。
莫队二次离线的一些限制
莫队二次离线有以下几种限制：
- 当前答案不会影响下一次修改的决策（我就没见过这种情况，有见过的大佬讨论区发一下，谢谢）。
- 满足 \(F(x,[l,r])=f(x,r)-f(x,l-1)\)。
当然，假如 \(O(k)=O(1)\) 的话，你也没有必要进行莫队二次离线。
莫队二次离线（空间 \(O(n\sqrt n)\)）
我们先考虑右指针右移的情况。
设当前右指针为 \(r\)，左指针为 \(l\)，那么一次右指针右移操作对 \(ans\) 的贡献即为 \(F_{r+1,[l,r]}\)，同时 \(r\to r+1\)。
根据限制 2，我们可以将贡献差分为 \(f_{r+1,r}-f_{r+1,l-1}\)。
同理，右端点左移的贡献就是 \(f_{r,l-1}-f_{r,r-1}\)，左端点右移的贡献就是 \(f_{l,l}-f_{l,r}\)，左端点左移的贡献就是 \(f_{l-1,r}-f_{l-1,l-1}\)。
我们在移动端点的同时，记录这些需要求的贡献，然后在遍历序列的同时进行求解即可。
例如模板题 luogu4887，普通莫队的时间复杂度为 \(O(\binom{14}kn+n\sqrt n)\)，空间复杂度平颈为记录所有贡献，为 \(O(n\sqrt n)\)。这样并不能通过此题，因为时间常数和空间过大了。但还是附上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=(1<<14);
int n,m,k,a[N],c[M],cn,tg[M],nw1[N],nw2[N];
struct que2{int x,id,v;};vector<que2>qe[N];
struct que1{int l,r,id;}qu[N];ll ans[N];
int cmp(que1 x,que1 y){if(x.l/300!=y.l/300) return x.l/300<y.l/300;if((x.l/300)&1) return x.r>y.r;return x.r<y.r;
}void dfs(int x,int now,int num){if(x>14) return;if(num==k) return c[++cn]=now,void();dfs(x+1,now|(1<<x),num+1),dfs(x+1,now,num);
}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m>>k,dfs(0,0,0);//这个马上讲for(int i=1;i<=n;i++){cin>>a[i],nw1[i]=tg[a[i]];for(int j=1;j<=cn;j++)tg[a[i]^c[j]]++;nw2[i]=tg[a[i]];}//塞入贡献for(int i=1;i<=m;i++)cin>>qu[i].l>>qu[i].r,qu[i].id=i;memset(tg,0,sizeof(tg));sort(qu+1,qu+m+1,cmp);for(int i=1,l=1,r=0;i<=m;i++){while(r>qu[i].r){ans[qu[i].id]-=nw1[r];qe[l-1].push_back({r--,qu[i].id,1});}while(l<qu[i].l){ans[qu[i].id]+=nw2[l];qe[r].push_back({l++,qu[i].id,-1});}while(r<qu[i].r){ans[qu[i].id]+=nw1[++r];qe[l-1].push_back({r,qu[i].id,-1});}while(l>qu[i].l){ans[qu[i].id]-=nw2[--l];qe[r].push_back({l,qu[i].id,1});}}//求解贡献for(int i=1;i<=n;i++){for(int j=1;j<=cn;j++) tg[a[i]^c[j]]++;for(auto x:qe[i]) ans[x.id]+=x.v*tg[a[x.x]];}//注意到我们算的是增量，所以还要再做一次前缀和for(int i=1;i<=m;i++)ans[qu[i].id]+=ans[qu[i-1].id];for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";return 0;
}
真·莫队二次离线
发现实际上我们可以将贡献分为两部分：\(f(x,x)/f(x,x-1)\) 和 \(f(x,l-1)/f(x,r)\)。
前面两个最多只有 \(O(n)\) 种确定情况，可以预处理。
而后面两个，我们仍然挑选右指针右移进行举例。设当前右指针为 \(r\)，目标位置为 \(R\)，则实际上所有 \(f(x,l-1)\) 的贡献可以表示为 \(\sum\limits_{i=R+1}^rf(i,l-1)\)。那么我们可以将所有的状态 \((x,l-1)\) 压缩成一个新状态 \((R+1,r,l-1)\)。这样我们就可以用总计 \(O(n)\) 的状态数记录贡献。时间常数和空间都大大降低了。
最终，真·二次离线莫队的时空复杂度为 \(O(nk+n\sqrt n),O(n)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=(1<<14);
int n,m,k,a[N],c[M],cn,tg[M];ll nw1[N],nw2[N];
struct que2{int l,r,id,v;};vector<que2>qe[N];
struct que1{int l,r,id;}qu[N];ll ans[N];
int cmp(que1 x,que1 y){if(x.l/300!=y.l/300) return x.l/300<y.l/300;if((x.l/300)&1) return x.r>y.r;return x.r<y.r;
}void dfs(int x,int now,int num){if(x>14) return;if(num==k) return c[++cn]=now,void();dfs(x+1,now|(1<<x),num+1),dfs(x+1,now,num);
}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m>>k,dfs(0,0,0);for(int i=1;i<=n;i++){cin>>a[i],nw1[i]=tg[a[i]];for(int j=1;j<=cn;j++)tg[a[i]^c[j]]++;nw2[i]=tg[a[i]];nw1[i]+=nw1[i-1],nw2[i]+=nw2[i-1];}for(int i=1;i<=m;i++)cin>>qu[i].l>>qu[i].r,qu[i].id=i;memset(tg,0,sizeof(tg));sort(qu+1,qu+m+1,cmp);for(int i=1,l=1,r=0;i<=m;i++){if(r>qu[i].r){qe[l-1].push_back({qu[i].r+1,r,qu[i].id,1});ans[qu[i].id]-=nw1[r]-nw1[qu[i].r],r=qu[i].r;}if(l<qu[i].l){qe[r].push_back({l,qu[i].l-1,qu[i].id,-1});ans[qu[i].id]+=nw2[qu[i].l-1]-nw2[l-1],l=qu[i].l;}if(r<qu[i].r){qe[l-1].push_back({r+1,qu[i].r,qu[i].id,-1});ans[qu[i].id]+=nw1[qu[i].r]-nw1[r],r=qu[i].r;}if(l>qu[i].l){qe[r].push_back({qu[i].l,l-1,qu[i].id,1});ans[qu[i].id]-=nw2[l-1]-nw2[qu[i].l-1],l=qu[i].l;}}for(int i=1;i<=n;i++){for(int j=1;j<=cn;j++) tg[a[i]^c[j]]++;for(auto x:qe[i])for(int j=x.l;j<=x.r;j++) ans[x.id]+=x.v*tg[a[j]];}for(int i=1;i<=m;i++)ans[qu[i].id]+=ans[qu[i-1].id];for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";return 0;
}