二次离线莫队问题

解题思路

本题有若干个询问，每个询问都要求出某个区间中异或和在二进制表示中有 $k$ 个 $1$ 的数对个数。

我们规定，如果某两个数的异或和在二进制表示中有 $k$ 个 $1$，我们就称这两个数是配对的，因此每个询问就变成了求某个区间中有多少数对是配对的。

本题需要用到二次离线莫队来做，而二次离线莫队就是一共需要离线两次来做，在做莫队时，我们每次都会对一段区间去查询一个数，然后我们都会去对两个端点进行移动，然后在新的维护区间中去求我们的询问。

而对于二次离线莫队，就是当我们每次更新完维护区间之后，对于区间的询问很难算，所以我们需要在每次更新完维护区间之后，再把当前询问单独拎出来再重新离线求当前询问的值。二次离线算法思维难度一般不高，但是代码实现中的细节非常多，且每道题都需要重新思考，可以说是非常恶心。

要想使用莫队算法来求，那么每次我们都需要从上一个询问区间 $[l, r]$ 的信息快速得到当前询问区间 $[L, R]$ 的信息。以右端点 $r$ 为例，当 $r$ 右移后，我们需要将 $w_{r+1}$ 加入到维护区间中，那么我们就需要考虑将 $w_{r+1}$ 加入到维护区间中后，维护区间的信息该怎么去维护。当我们将 $w_{r+1}$ 加入后，需要求一下它对于配对的数量有什么样的影响，显然配对的数量只会增加，至于增加的数量，就是 $[l, r]$ 中和 $w_{r+1}$ 配对的数的个数，这一步可以用前缀和来求。

设 $S_i$ 表示 $w_1 \sim w_i$ 中有多少个数和 $w_{r+1}$ 配对，此时对于 $[l, r]$ 中和 $w_{r+1}$ 配对的数的个数就是 $S_r-S_{l-1}$。接下来就是要求 $S_r$ 和 $S_{l-1}$，对于 $S_r$，其实是问 $w_1 \sim w_r$ 中有多少个数和 $w_{r+1}$ 配对，可以发现要询问的数就是区间的后一个数，而 $S_{l-1}$ 则没有这么好的性质，$w_{l-1}$ 和 $w_{r+1}$ 之间的距离是非常随机的，毫无规律可循，因此 $S_r$ 和 $S_{l-1}$ 其实是两类询问，分两种情况来考虑。

首先对于 $S_r$，由于这一部分是非常有规律的，所以可以提前预处理，设 $f_i$ 表示 $w_1 \sim w_i$ 中与 $w_{i+1}$ 配对的数个数，而 $S_r$ 显然就是 $f_i$，因此我们需要快速的预处理出 $f_i$，可以用一个 $g_x$ 表示前 $i$ 个数中有多少个数与 $x$ 配对。当我们把 $g_x$ 预处理出来，则 $f_i = g_{w_{i+1}}$。

因此我们现在就是需要求出 $i$ 阶段的 $g_x$，假设当前 $g_x$ 表示前 $i-1$ 个数中有多少个数与 $x$ 配对，这里我们可以先预处理出 $0 \sim 2^{14}-1$ 中所有有 $k$ 个 $1$ 的数 $y_i$，我们想从前 $i-1$ 个数的 $g_x$ 变成前 $i$ 个数的 $g_x$，相当于是加入了一个新的数 $w_i$，此时我们只要找出所有和 $w_i$ 配对的 $x$，令 $g_x+1$，最终就能得到前 $i$ 个数的 $g_x$，而我们要找的所有 $x$ 则必须满足 $w_i~xor~x=y_i$，这个条件等价于 $x=w_i~xor~y_i$，因此我们可以枚举所有不同的 $y_i$，通过 $y_i~xor~w_i$ 计算出所有的 $x$，因为 $y_i$ 不同，所以得出的 $x$ 也不同。

综上所述，对于前 $i-1$ 个数的 $g_x$，我们枚举所有 $y_i$，令 $g_{y_i~xor~w_i}+1$，最终就能得到前 $i$ 个数的 $g_x$，然后再用 $g_x$ 计算 $f_i$ 即可。这样我们就能用 $g_x$ 作为辅助递推得出所有的 $f_i$。这一部分预处理一共只需要做一次，由于 $k$ 比较小，$y_i$ 最多只有三千多个，因此预处理的计算量最多只有三千多万。

接下来我们需要想办法求出 $S_{l-1}$，$S_r$ 通过我们刚才的分析，我们可以在做莫队的过程中在线求出来，但是 $S_{l-1}$ 并不能马上求出来，因此我们只能先将所有要求 $S_{l-1}$ 的问题先找出来，然后我们再离线把所有要求的 $S_{l-1}$ 求出来，最后我们才能求出 $S_r - S_{l-1}$。

要求 $S_{l-1}$，其实就是求 $w_1 \sim w_{l-1}$ 中有多少个数是和 $w_{r+1}$ 配对的，以此类推，在从 $r$ 移动到 $R$ 的过程中，我们会将 $r+1,r+2,…,R$ 都加入到维护区间中，因此对于 $\forall x \in [r+1,R]$，都要求出 $w_1 \sim w_{l-1}$ 中和 $w_x$ 配对的数的个数，可以发现这些问题都是问某个固定前缀中，某个区间的每个数和这个前缀中有多少个数配对。我们可以将这些询问全部找出来，然后按照从前往后的顺序计算所有询问，我们先算一下所有前缀是 $1$ 的询问，再算一下所有前缀是 $2$ 的询问，以此类推，直到我们算完所有前缀是 $l-1$ 的询问后，我们就将所有的询问都处理完了。

由于我们是从前往后做所有询问，因此每一次前缀中只会增加一个数，因此这里我们同样可以用一个 $g_x$ 数组来作为辅助，表示的内容和上面相同，同样表示前 $i$ 个数中与 $x$ 配对的数的个数，因此对于 $\forall x \in [r+1,R]$，我们想求的 $w_1 \sim w_{l-1}$ 中和 $x$ 配对的数的个数恰好就是 $g_x$，直接按照上面更新 $g_x$ 的思路依次往后求即可。而这一部分的询问数量应该取决于两个指针移动的次数，这个在基础莫队中就已经证明过是 $O(\sqrt{n})$ 级别的，因此我们就能用一个 $O(n\sqrt{n})$ 的离线做法求出所有的 $S_{l-1}$，然后就能把这部分在莫队中无法解决的问题统一计算出来。

到此我们就能将前一个询问到当前询问的增量 $S_r-S_{l-1}$ 求出来，但是这并不是当前询问的答案，如果我们想求某一个询问的结果的话，还需要将前面求出来的所有增量累加成前缀和才是最终答案。

注意，上面我们推导了 $r$ 向右移动到 $R$ 这一种情况，实际上两个指针一共有四种情况，而其他三种情况都按照上面同样的形式去分析即可，代码实现时需要根据每种情况的区别做一些更细致的处理，这里就不过多赘述，直接体现在代码中。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 100010;

struct Query
{
    int id, l, r; //编号、左端点、右端点
    LL ans; //由于每个询问的答案可能分成多个部分分别处理，需要先将部分答案单独存下来
}q[N]; //存储所有询问

struct Range
{
    int id, l, r, t; //编号、左端点、右端点、类型（1 表示加上，-1 表示减去）
};
//range[i] 表示询问 w[l] ~ w[r] 中每个数和 w[1] ~ w[i] 共有多少个配对
vector<Range> range[N]; //存储每个询问中需要二次离线解决的问题

int n, m, k, len;
int w[N]; //原序列
int id[N]; //记录每个下标所在的块编号
LL res[N]; //记录每个询问的答案
//f[i] 表示 w[1] ~ w[i] 中与 w[i + 1] 配对的数的个数
//g[x] 表示前 i 个数中与 x 配对的数的个数
int f[N], g[N];

inline int get_count(int x) //计算 x 的二进制表示中 1 的个数
{
    int res = 0;
    for(int i = 0; i < 14; i++) res += x >> i & 1;
    return res;
}

//先按照左端点所在块的编号从小到大排序，再按照右端点从小到大排序
bool cmp(const Query &a, const Query &b)
{
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
    return a.r < b.r;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);

    vector<int> nums; //存储所有二进制表示中有 k 个 1 的数
    for(int i = 0; i < 1 << 14; i++) //枚举范围内的所有数
        if(get_count(i) == k) //如果当前数的二进制表示中有 k 个 1
            nums.push_back(i); //将当前数加入容器

    //预处理 f[]
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < nums.size(); j++) g[w[i] ^ nums[j]]++;
        f[i] = g[w[i + 1]];
    }

    len = sqrt(n); //计算块的长度
    for(int i = 1; i <= n; i++) id[i] = (i - 1) / len; //预处理每个下标所在的块编号

    //接收所有询问
    for(int i = 0; i < m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }

    //将所有询问先按照左端点所在块的编号从小到大排序，再按照右端点从小到大排序
    sort(q, q + m, cmp);

    //莫队算法
    for(int x = 0, i = 1, j = 0; x < m; x++)
    {
        int l = q[x].l, r = q[x].r;

        //j 向右移向 r，则 [j + 1, r] 中的所有 -S[i - 1] 需要二次离线处理
        if(j < r) range[i - 1].push_back({x, j + 1, r, -1});
        while(j < r) q[x].ans += f[j++]; //j 向右移向 r，加入 w[j + 1]，ans + (S[j] - S[i - 1])

        //j 向左移向 r，则 [r + 1, j] 中的所有 +S[i - 1] 需要二次离线处理
        if(j > r) range[i - 1].push_back({x, r + 1, j, 1});
        while(j > r) q[x].ans -= f[--j]; //j 向左移向 r，删去 w[j]，ans - (S[j - 1] - S[i - 1])

        //i 向右移向 l，则 [i, l - 1] 中的所有 -S[j] 需要二次离线处理
        if(i < l) range[j].push_back({x, i, l - 1, -1});
        while(i < l) q[x].ans += f[i - 1] + !k, i++; //i 向右移向 l，删去 w[i]，ans - (S[j] - S[i])

        //i 向左移向 l，则 [l, i - 1] 中的所有 +S[j] 需要二次离线处理
        if(i > l) range[j].push_back({x, l, i - 1, 1});
        while(i > l) q[x].ans -= f[i - 2] + !k, i--; //i 向左移向 l，加入 w[i - 1]，ans + (S[j] - S[i - 1])
    }

    memset(g, 0, sizeof g); //g[] 数组复用，提前清空

    //二次离线
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < nums.size(); j++) g[w[i] ^ nums[j]]++; //递推出前 i 个数的 g[]
        for(int j = 0; j < range[i].size(); j++) //处理所有和 1 ~ i 求配对的询问
        {
            int num = range[i][j].id, l = range[i][j].l, r = range[i][j].r, t = range[i][j].t;
            for(int x = l; x <= r; x++) q[num].ans += g[w[x]] * t; //将求出的结果加入对应询问的答案中
        }
    }

    for(int i = 1; i < m; i++) q[i].ans += q[i - 1].ans; //前缀和求出所有询问的最终答案
    for(int i = 0; i < m; i++) res[q[i].id] = q[i].ans; //记录所有询问的答案

    for(int i = 0; i < m; i++) printf("%lld\n", res[i]); //输出所有询问的答案

    return 0;
}