P4887 【模板】莫队二次离线（第十四分块(前体)）
题意：
询问区间内最多有几对数，异或起来恰好有k个1
思路：
- 莫队离线移动为 $ O( n \sqrt n ) $
- 数值最多为 $ 2^{14} $ ,即最多有14个1，可以暴力枚举
- 定义 $ f_i $ 表示 $ 1到i-1有多少个数与i+1配对 $
- 定义 $ g_i $ 表示 $ 能与i配对的数的数量 ,f_i=g_{w_i}$
- 可以暴力计算 $ f $
- 原区间为 $ l,r $
- 假设 $ r<qr $,那么假设前缀和 $ S_i $ 表示 $ 1到i与 w_r配对的数 $ ,那么 $ res+=S_{r+1}-S_{l-1}=f_r-S_{l-1} $,对于区间 $ [r+1,qr] 都要算一遍对应的S_{l-1} $，这个是不能直接算的需要离线下来算，即二次离线
- 同理，有以下
- $ r>qr ,res-=S_{r}-S_{l-1}=f_{r-1}-S_{l-1},对于所有区间r∈[qr+1,r] $
- $ l<ql,res-=S_r-S{l-1}=S_r-(f_{l-1}+!k),对于所有l∈[l,ql-1] $
- $ l>ql,res+=S_r-S_{l-2}=S_r-(f_{l-2}+!k),对于所有l∈[ql,l-1] $
- 对于离线下来的range暴力求，本质上是移动l，r指针的贡献，为 $ n \sqrt n $
- 最后再进行累加，因为求的是相对变化
cpp
int be[M],block,tot;
struct Q{
int id,l,r,res;
};
struct Range{
int i,l,r,p;
};
bool cmp(Q &x,Q &y){
return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:((be[x.l]&1)?x.r<y.r:x.r>y.r);
}
void solve(){
int n,m,k;
cin>>n>>m>>k;
vector<int> w(n+10),f(n+10),g(2e4);
for(int i=1;i<=n;i++)cin>>w[i];
vector<Q> q;
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
q.push_back({i,l,r,0});
}
if(k>14){
for(int i=0;i<m;i++)cout<<"0\n";
return;
}
block=sqrt(n),tot=(n+block-1)/block;
for(int i=1;i<=tot;i++){
int l=(i-1)*block+1,r=min(n,i*block);
for(int j=l;j<=r;j++)be[j]=i;
}
sort(q.begin(),q.end(),cmp);
vector<int> nums;
for(int i=0;i<1<<14;i++){
if(__builtin_popcount(i)==k)nums.push_back(i);
}
for(int i=1;i<=n;i++){
for(auto it:nums)g[w[i]^it]++;
f[i]=g[w[i+1]];
}
vector<Range> range[n+1];
for(int i=0,l=1,r=0;i<m;i++){
auto &[id,ql,qr,res]=q[i];
if(r<qr)range[l-1].push_back({i,r+1,qr,-1});
while(r<qr)res+=f[r++];
if(r>qr)range[l-1].push_back({i,qr+1,r,1});
while(r>qr)res-=f[--r];
if(l<ql)range[r].push_back({i,l,ql-1,-1});
while(l<ql)res+=f[l-1]+!k,l++;
if(l>ql)range[r].push_back({i,ql,l-1,1});
while(l>ql)res-=f[l-2]+!k,l--;
}
g.assign(2e4,0);
for(int i=1;i<=n;i++){
for(auto it:nums)g[w[i]^it]++;
for(auto [id,l,r,p]:range[i]){
for(int x=l;x<=r;x++)q[id].res+=g[w[x]]*p;
}
}
vector<int> ans(m);
for(int i=1;i<m;i++)q[i].res+=q[i-1].res;
for(int i=0;i<m;i++)ans[q[i].id]=q[i].res;
for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}