莫队二次离线，是由数据结构题之神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])\)。

莫队二次离线的一些限制

莫队二次离线有以下几种限制：

1. 当前答案不会影响下一次修改的决策（我就没见过这种情况，有见过的大佬讨论区发一下，谢谢）。
2. 满足 \(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; }