第一发根号科技
# 引入
最外层为莫队问题——每次查询一个区间内的答案，内层查询的内容为给定区间内的点对 $(i,j)$ 数量。常规的莫队做法就是再用一个数据结构（通常复杂度不为 $O(1)$）来计算当前区间向左右扩展或缩小后，新增或减少的贡献。
比如下面这个模板问题：
> Linked 洛谷 P4887
点击展开/折叠 题面
给定序列 $a$，每次查询给一个区间 $[l,r]$ 查询 $l\leq i< j\leq r$，且 $a_i\oplus a_j$ 的二进制表示下有 $k$ 个 $1$ 的二元组 $(i,j)$ 的个数。$\oplus$ 是指按位异或。
首先我们有朴素算法：统计当前区间内每个值 $i$ 的出现次数 $tot_i$。每次区间扩展/缩小时，设发生变动的数字为 $a_t$，则枚举二进制下有 $k$ 个 $1$ 的数字 $c$（我们发现 $c$ 的个数最多只有 $C_{14}^7$，差不多是 $\sqrt n$），求 $\sum tot_{a_t\oplus c}$。
这样复杂度是 $O(n^2)$ 的。
# 二次离线莫队
- 时间复杂度优化
其实我们可以想办法降低插入的效率并且提高查询的效率，达到一个美妙的平衡。
这就是二次离线莫队。
从字面上理解，两次离线，第一次是莫队，第二次是？扫描线——莫队算法进行时，产生了一些区间查询的子问题。比如模板问题中，每次扩展或缩小区间的时候，要计算发生变动的数 $a_t$ 对当前区间 $[L,R]$ 的贡献。
第二次离线就是把这些区间询问做扫描线，即把区间 $[L,R]$ 拆成 $[1,R]-[1,L-1]$。就只需要维护前缀的 $tot_i$，每扫到一个询问，就 $O(\sqrt n)$ 查询。
优化到这里，插入次数只有 $n$，查询次数是 $O(n\sqrt n)$ 的。时间复杂度仍然是 $O(n^2)$。
我们发现这样很亏……因为次数较少的插入是 $O(1)$ 的，而次数较多的查询反而是 $O(\sqrt n)$ 的。
于是我们考虑让插入变成 $O(\sqrt n)$ 的！$tot_i$ 原来维护的是前缀的 $i$ 的个数，而现在我们改成计算贡献的方法——$tot_i$ 维护前缀中，与 $i$ 可以匹配成一个要求的数对的数的数量。
也比较简单，加入数 $a_t$ 时，对于每个二进制下有 $k$ 个 $1$ 的 $c$，$tot_{a_t\oplus c}:=tot_{a_t\oplus c}+1$。
于是这样的时间复杂度就降为了 $O(n\sqrt n)$。
你以为出题人就这样放过你了？还要卡空间，现在的空间复杂度是 $O(n\sqrt n)$ 的，因为要把莫队产生的 $O(n\sqrt n)$ 次询问打上标记。
- 空间复杂度优化
具体考虑莫队算法中每种区间改变产生的区间询问（设原始区间为 $[L,R]$）：
- $R$ 右移，计算 $R+1$ 对 $[L,R]$ 的贡献；
- $L$ 左移，计算 $L-1$ 对 $[L,R]$ 的贡献；
- $R$ 左移，计算 $R$ 对 $[L,R-1]$ 的贡献；
- $L$ 右移，计算 $L$ 对 $[L+1,R]$ 的贡献；
设 $f(i,j)$ 表示 $k\in[1,i]$ 中 $a_k$，能够和 $a_j$ 异或得到二进制下有 $k$ 个 $1$ 的数的数量。
则上面的四种询问可以拆成：
- $R$ 右移到 $R’$，$\sum\limits_{r=R}^{R’-1}f(r,r+1)-f(L-1,r+1)$；
- $L$ 左移到 $L’$，$\sum\limits_{l=L’+1}^Lf(R,l-1)-f(l-1,l-1)$；
- $R$ 左移到 $R’$，$\sum\limits_{r=R’+1}^Rf(r-1,r)-f(L-1,r)$；
- $L$ 右移到 $L’$，$\sum\limits_{l=L}^{L’-1}f(R,l)-f(l,l)$；
我们发现 $f(i,i)=f(i-1,i)-[k=0]$，当 $k=0$ 的时候特判一下，其他情况下 $f(i,i)=f(i-1,i)$。
于是四种询问的式子可以分成两类：
- $\sum\limits_{i=i_0}^{i_1}f(i-1,i)$，可以前缀和处理；
- $\sum\limits_{i=i_0}^{i_1}f(j,i)$，在 $j$ 的位置打上 $[i_0,i_1]$ 的查询标记。
这样就把 $O(n\sqrt n)$ 的标记降成了 $O(n)$ 个标记。空间复杂度也降下来了。
# 源代码
（模板题，略微有点卡常）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85/*Lucky_Glass*/
using namespace std;
typedef long long ll;
const int N=1e5+10,ALL=(1<<14),BL=320;
struct DATA{
int le,ri,id;
DATA(){}
DATA(ci l,ci r,ci i):le(l),ri(r),id(i){}
};
int n,m,d,nT;
vector<DATA> ref[N];
int qry[N][2],idq[N],cnt[ALL],num[N],t[N];
ll ans[N],pref[N];
inline bool cmp(ci a,ci b){
int ia=qry[a][0]/BL,ib=qry[b][0]/BL;
if(ia!=ib) return ia<ib;
if(ia&1) return qry[a][1]>qry[b][1];
else return qry[a][1]<qry[b][1];
}
inline int Cnt(reg x){int ret=0;while(x)x^=lowbit(x),ret++;return ret;}
int main(){
scanf("%d%d%d",&n,&m,&d);
for(reg i=1;i<=n;i++) scanf("%d",&num[i]);
for(reg i=1;i<=m;i++)
idq[i]=i,scanf("%d%d",&qry[i][0],&qry[i][1]);
sort(idq+1,idq+1+m,cmp);
//
for(reg i=0;i<ALL;i++)
if(Cnt(i)==d) t[++nT]=i;
for(reg i=1;i<=n;i++){
pref[i]=cnt[num[i]]+pref[i-1];
for(reg j=1;j<=nT;j++) cnt[t[j]^num[i]]++;
}
//
for(int I=1,Le=1,Ri=0;I<=m;I++){
int i=idq[I],le=qry[i][0],ri=qry[i][1];
if(Le>le){
ref[Ri].push_back(DATA(le,Le-1,i));
ans[i]-=pref[Le-1]-pref[le-1];
if(!d) ans[i]-=Le-le;
Le=le;
}
if(Ri<ri){
ref[Le-1].push_back(DATA(Ri+1,ri,-i));
ans[i]+=pref[ri]-pref[Ri];
Ri=ri;
}
if(Le<le){
ref[Ri].push_back(DATA(Le,le-1,-i));
ans[i]+=pref[le-1]-pref[Le-1];
if(!d) ans[i]+=le-Le;
Le=le;
}
if(Ri>ri){
ref[Le-1].push_back(DATA(ri+1,Ri,i));
ans[i]-=pref[Ri]-pref[ri];
Ri=ri;
}
}
//
memset(cnt,0,sizeof cnt);
for(reg i=1;i<=n;i++){
for(reg j=1;j<=nT;j++) cnt[t[j]^num[i]]++;
for(auto j:ref[i])
for(reg k=j.le;k<=j.ri;k++)
if(j.id>0) ans[j.id]+=cnt[num[k]];
else ans[-j.id]-=cnt[num[k]];
}
for(reg i=1;i<=m;i++)
ans[idq[i]]+=ans[idq[i-1]];
for(reg i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}
THE END
Thanks for reading!
> Linked 零和Zero-Sum-Bilibili