视频链接：
Luogu P4887 【模板】莫队二次离线（第十四分块(前体)）
// 莫队二次离线 O(n*sqrt(n)+n*C(k,14))
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N=100005;
int n,m,k,B,block[N],a[N],t[N],pre[N];
long long ans[N];
vector<int> b; //二进制中1的个数为k的数
struct F{
int id,l,r,z;
};
vector<F> f[N]; //待求贡献的信息
struct Q{
int id,l,r;
long long ans;
bool operator<(Q &x){
if(block[l]!=block[x.l])return l<x.l;
return r<x.r;
}
}q[N];
int count(int x){ //x的二进制中1的个数
int s=0;
while(x) s+=x&1,x>>=1;
return s;
}
int main(){
scanf("%d%d%d",&n,&m,&k); B=sqrt(n);
for(int i=1;i<=n;i++)
scanf("%d",a+i),block[i]=(i-1)/B+1;
for(int i=1,l,r;i<=m;i++)
scanf("%d%d",&l,&r),q[i]={i,l,r};
sort(q+1,q+m+1);
for(int i=0;i<1<<14;++i)
if(count(i)==k)b.push_back(i); //最多C(7,14)=3432
for(int i=1;i<=n;i++){
pre[i]=t[a[i]];//a1~a[i-1]与ai异或有k个1的数的个数
for(auto x:b) ++t[a[i]^x];
}
for(int i=1,l=1,r=0;i<=m;i++){ //莫队
//r右移:f(l,x-1)=f(1,x-1)-f(1,l-1), x~[r+1,qr]
if(r<q[i].r) f[l-1].push_back({i,r+1,q[i].r,-1});
while(r<q[i].r) q[i].ans+=pre[++r];
//r左移:-f(l,x-1)=-(f(1,x-1)-f(1,l-1)), x~[qr+1,r]
if(r>q[i].r) f[l-1].push_back({i,q[i].r+1,r,1});
while(r>q[i].r) q[i].ans-=pre[r--];
//l左移:f(x+1,r)=f(1,r)-f(1,x), x~[ql,l-1]
if(l>q[i].l) f[r].push_back({i,q[i].l,l-1,1});
while(l>q[i].l) q[i].ans-=pre[--l]+!k;
//l右移:-f(x+1,r)=-(f(1,r)-f(1,x)), x~[l,ql-1]
if(l<q[i].l) f[r].push_back({i,l,q[i].l-1,-1});
while(l<q[i].l) q[i].ans+=pre[l++]+!k;
}
//二次离线，累计f(1,l-1)和f(1,r)的贡献
memset(t,0,sizeof(t));
for(int i=1,id,l,r,z;i<=n;i++){ //扫描ai
for(auto& x:b) ++t[a[i]^x]; //与ai配对的数均+1
for(auto& y:f[i]){ //以ai为边界的f
for(int x=y.l;x<=y.r;x++)
q[y.id].ans+=y.z*t[a[x]]; //累计配对贡献
}
}
//后一个查询是前一个查询的增量，故求前缀和
for(int i=2;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]);
}
// 莫队二次离线 O(n*sqrt(n)+n*C(k,14))
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <tuple>
using namespace std;
const int N=100005;
int n,m,k,B,block[N],a[N],t[N],pre[N];
long long ans[N];
vector<int> b; //二进制中1的个数为k的数
vector<tuple<int,int,int,int>> f[N]; //待求贡献的信息
struct Q{
int id,l,r;
long long ans;
bool operator<(Q &x){
if(block[l]!=block[x.l])return l<x.l;
return r<x.r;
}
}q[N];
int main(){
scanf("%d%d%d",&n,&m,&k); B=sqrt(n);
for(int i=1;i<=n;i++)
scanf("%d",a+i),block[i]=(i-1)/B+1;
for(int i=1,l,r;i<=m;i++)
scanf("%d%d",&l,&r),q[i]={i,l,r};
sort(q+1,q+m+1);
for(int i=0;i<1<<14;++i) //b内最多C(7,14)=3432
if(__builtin_popcount(i)==k)b.push_back(i);
for(int i=1;i<=n;i++){
pre[i]=t[a[i]];//a1~a[i-1]与ai异或有k个1的数的个数
for(auto x:b) ++t[a[i]^x];
}
for(int i=1,l=1,r=0;i<=m;i++){ //莫队
//r右移:f(l,x-1)=f(1,x-1)-f(1,l-1), x~[r+1,qr]
if(r<q[i].r) f[l-1].emplace_back(i,r+1,q[i].r,-1);
while(r<q[i].r) q[i].ans+=pre[++r];
//r左移:-f(l,x-1)=-(f(1,x-1)-f(1,l-1)), x~[qr+1,r]
if(r>q[i].r) f[l-1].emplace_back(i,q[i].r+1,r,1);
while(r>q[i].r) q[i].ans-=pre[r--];
//l左移:f(x+1,r)=f(1,r)-f(1,x), x~[ql,l-1]
if(l>q[i].l) f[r].emplace_back(i,q[i].l,l-1,1);
while(l>q[i].l) q[i].ans-=pre[--l]+!k;
//l右移:-f(x+1,r)=-(f(1,r)-f(1,x)), x~[l,ql-1]
if(l<q[i].l) f[r].emplace_back(i,l,q[i].l-1,-1);
while(l<q[i].l) q[i].ans+=pre[l++]+!k;
}
//二次离线，累计f(1,l-1)和f(1,r)的贡献
memset(t,0,sizeof(t));
for(int i=1,id,l,r,z;i<=n;i++){ //扫描ai
for(auto& x:b) ++t[a[i]^x]; //与ai配对的数均+1
for(auto& y:f[i]){ //以ai为边界的f
std::tie(id,l,r,z)=y; //元组的赋值
for(int x=l;x<=r;x++) //累计配对贡献
q[id].ans+=z*t[a[x]];
}
}
//后一个查询是前一个查询的增量，故求前缀和
for(int i=2;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]);
}
P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
P5501 [LnOI2019] 来者不拒，去者不追 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
标签：二次,int,离线,long,ans,include,莫队 From： https://www.cnblogs.com/dx123/p/18130171