题解 P4887 【【模板】莫队二次离线（第十四分块(前体)）】
FutaRimeWoawaSete
·
·
题解
二次离线莫队，听着好像很难的样子而且也是个黑模板，其实如果你学的快真的看代码都能看懂。
适用范围在第一篇题解的基础上完善了一下：
- 首先可以滚莫队，这是废话；
- 接着就是我们很难在比较快的时间里完成区间递推；这里其实可以类比回滚莫队，只不过回滚莫队可能是一种操作很简单另一种操作无法实现或者很慢，而我们二次离线莫队是两种操作都很慢……
- 在第二种的基础上，我们设 f(x , [l,r]) 表示序列中第 x 个元素对区间 [l,r] 的贡献，满足两个性质：f(x , [l,r]) = f(x , [1 , r]) - f(x , [1 , l - 1]) 且 我们可以在很快的时间里计算出 f(i , [1 , i]) 。
其实二次离线莫队的要求还是很多的，而它的例题也是少的可怜……
那么首先来说一下二次离线莫队是个怎么大致操作的：
- 预处理出所有的 f(i , [1 , i]) 。
- 运用莫队滚动的特性：固定一个端点不动，另一个端点自由伸缩，将询问转化成前缀和的形式分成两部分计算：一部分用我们处理出的 f(i , [1 , i]) 计算 ， 还有一部分通过某种形式单独拿出来计算；
大家不要想为什么，先记一下大致的过程即可。
接着我们以此题举例，首先我们生搬硬套一个莫队上去,接着我们发现我们进行区间递推的时候发现，一次区间递推的时间复杂度是个组合数级别的时间复杂度……
现在我们肯定得想办法优化每次区间递推，我们想，莫队的 4 个 while 循环都是固定一个端点，另一个端点进行了左右伸缩，我们可不可以从这上面下手？
我们首先就思考一次区间递推，假设现在从 [l , r] -> [l , r + 1] 。
那么我们现在的答案肯定会有变动，也就是多了一个 f(r + 1 , [l , r]) 贡献。
那么我们拆拆拆，f(r + 1 , [l , r]) = f(r + 1 , [1 , r]) - f(r + 1 , [1 , l - 1]) ， 诶我们发现前面这个东西有点特殊，后面的造成影响的区间是 [1 , r] ，询问的是第 r + 1 个元素，在此题中，这个玩意儿可以直接算啊！！！
现在我们在仔细想，现在不是在把右端点右移吗？假如区间 [l , r] -> [l , R] 的话呢？
我们记 r + 1 \leq x \leq R ，那么我们现在就需要计算所有的：
那么现在，我们假设只管当前的答案变化了多少，最后对于所有的询问推一个前缀和，就可以获得所有询问的答案。首先我们在莫队中，肯定可以把我们前面这一坨东西给直接算出来，现在就想怎么搞后面的东西，我们又惊奇地发现我们后面的询问， $x$ 都是对 $[1 , l - 1]$ 这个区间造成影响，这个区间左端点是 $1$ ，右端点是 $l - 1$，那么我们只需要把这些询问又都再存一下，然后再跑一个前缀，在得到 $[1 , l - 1]$ 这个区间的信息时就可以查询了吗？
其他三种情况也同理，我们都可以进行这么转换，论实现的话，你对序列中的每个元素开个 $vector$ ，存到它下面就可以了，不过这样的空间是 $O(m \sqrt n)$ 的，我们还可以直接用个多元祖(可以见@gxy001的题解里面)存下来，就把空间复杂度压到了 $O(2m)$ 了。
以上就是二次离线莫队的步骤，对于此题，我们发现伟大的毒瘤 $lxl$ 又压了值域，所有我们可以直接预处理 $0 \sim 16384$ 里面的所有有 $k$ 个 $1$ 的数字存入 $b$ 数组，然后做前缀时，我们开个桶 $t$ 表示此时 $t_i$ 在对应的当前这个前缀区间中与多少个数按位异或起来的值有 $k$ 个 $1$ ，每次更新时枚举一边 $b$ 数组里面的所有数，使 $t_{a_i \operatorname{xor} b_j} ＋ 1$ 即可。
对于这道题，我们还要特判一下 $k = 0$，具体见代码。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Len = 4e5 + 5;
struct node
{
int l,r,idx;
int ans;
}Sec[Len];
struct Node
{
int l,r,idx,op;
};
vector<Node> q[Len];
vector<int> b;
int n,m,k,siz,a[Len],t[Len],p1[Len],block[Len];//p1:[1,{1 , l - 1}] , p2:[1,{1,l}]
int Print[Len];
bool cmp(const node &x,const node &y)
{
if(block[x.l] ^ block[y.l]) return block[x.l] < block[y.l];
return x.r < y.r;
}
int Count(int x)
{
int res = 0;
for( ; x ; x >>= 1) if(x & 1) res ++;
return res;
}
signed main()
{
scanf("%lld %lld %lld",&n,&m,&k);
if(k > 14)
{
for(int i = 1 ; i <= m ; i ++) puts("0");
return 0;
}
siz = sqrt(n);
for(int i = 0 ; i < 16384 ; i ++) if(Count(i) == k) b.push_back(i);
for(int i = 1 ; i <= n ; i ++)
{
scanf("%lld",&a[i]);
block[i] = (i - 1) / siz + 1;
}
for(int i = 1 ; i <= m ; i ++)
{
scanf("%lld %lld",&Sec[i].l,&Sec[i].r);
Sec[i].idx = i;
}
sort(Sec + 1 , Sec + 1 + m , cmp);
for(int i = 1 ; i <= n ; i ++)
{
p1[i] = t[a[i]];
for(int j = 0 ; j < b.size() ; j ++) t[a[i] ^ b[j]] ++;
}
memset(t , 0 , sizeof t);
int l = 1 , r = 0;
for(int i = 1 ; i <= m ; i ++)
{
if(l > Sec[i].l) q[r].push_back((Node){Sec[i].l , l - 1 , i , 1});
while(l > Sec[i].l) Sec[i].ans -= p1[-- l];
if(r < Sec[i].r) q[l - 1].push_back((Node){r + 1 , Sec[i].r , i , -1});
while(r < Sec[i].r) Sec[i].ans += p1[++ r];
if(l < Sec[i].l) q[r].push_back((Node){l , Sec[i].l - 1 , i , -1});//因为对于原来的答案而言，现在是要减去这些值，所以把原式取了个-1
while(l < Sec[i].l) Sec[i].ans += p1[l ++];
if(r > Sec[i].r) q[l - 1].push_back((Node){Sec[i].r + 1 , r , i , 1});//与上同
while(r > Sec[i].r) Sec[i].ans -= p1[r --];
}
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 0 ; j < b.size() ; j ++) t[a[i] ^ b[j]] ++;
for(int j = 0 ; j < q[i].size() ; j ++)
{
Node Calc = q[i][j];
for(int z = Calc.l ; z <= Calc.r ; z ++)
{
if(z <= i && k == 0) Sec[Calc.idx].ans += Calc.op * (t[a[z]] - 1);
else Sec[Calc.idx].ans += Calc.op * t[a[z]];
}
}
}
for(int i = 1 ; i <= m ; i ++) Sec[i].ans += Sec[i - 1].ans;
for(int i = 1 ; i <= m ; i ++) Print[Sec[i].idx] = Sec[i].ans;
for(int i = 1 ; i <= m ; i ++) printf("%lld\n",Print[i]);
return 0;
}
```