题解：二次离线莫队

一、题目分析

本题给定一个长度为(n)的序列和一个整数(k)，需要处理(m)次询问，每次询问一个区间([l, r])，要求找出满足(l\leq i < j\leq r)且(a_i\oplus a_j)（按位异或）的结果在二进制表示下恰好有(k)个(1)的数对((i, j))的数量。

二、解题思路

本题采用二次离线莫队算法来解决。先预处理出一些中间结果，然后利用莫队算法对询问区间进行排序和处理，通过记录区间的增减信息进行二次处理，从而计算出每个询问的答案。

（一）数据结构与变量定义

typedef long long LL;
const int N = 100010;
int n, m, k, len;
int w[N];
LL ans[N];
struct Query
{
    int id, l, r;
    LL res;
}q[N];
struct Range
{
    int id, l, r, t;
};
vector<Range> range[N];
int f[N], g[N];

• LL：定义长整型别名，用于处理较大的数值。
• N：定义序列长度和询问数量的最大值。
• n：存储序列的长度。
• m：存储询问的数量。
• k：存储按位异或结果中(1)的个数。
• len：存储分块的长度。
• w[N]：数组，用于存储序列的元素。
• ans[N]：数组，用于存储每个询问的答案。
• Query结构体：用于存储每个询问的信息，包括询问的编号id，区间左端点l，右端点r，以及当前计算的答案res。
• Range结构体：用于记录区间的增减信息，包括询问编号id，区间左端点l，右端点r，以及变化的符号t（(-1)表示减少，(1)表示增加）。
• range[N]：向量数组，用于存储每个位置相关的区间增减信息。
• f[N]和g[N]：数组，用于预处理和辅助计算。

（二）辅助函数

1. 计算二进制中(1)的个数函数get_count：

inline int get_count(int x)
{
    int res = 0;
    while (x) res += x & 1, x >>= 1;
    return res;
}

计算整数x在二进制表示下(1)的个数。

1. 获取元素所属块的编号函数get：

inline int get(int x)
{
    return x / len;
}

根据元素的下标x，返回其所属块的编号。

1. 询问排序比较函数cmp：

bool cmp(const Query& a, const Query& b)
{
    int i = get(a.l), j = get(b.l);
    if (i != j) return i < j;
    return a.r < b.r;
}

用于对询问进行排序。先按区间左端点所属块的编号排序，若块编号相同，则按区间右端点排序。

（三）主函数main

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    vector<int> nums;
    for (int i = 0; i < 1 << 14; i ++ )
        if (get_count(i) == k)
            nums.push_back(i);
    for (int i = 1; i <= n; i ++ )
    {
        for (auto y: nums) ++ g[w[i] ^ y];
        f[i] = g[w[i + 1]];
    }
    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }
    len = sqrt(n);
    sort(q, q + m, cmp);

    for (int i = 0, L = 1, R = 0; i < m; i ++ )
    {
        int l = q[i].l, r = q[i].r;
        if (R < r) range[L - 1].push_back({i, R + 1, r, -1});
        while (R < r) q[i].res += f[R ++ ];
        if (R > r) range[L - 1].push_back({i, r + 1, R, 1});
        while (R > r) q[i].res -= f[ -- R];
        if (L < l) range[R].push_back({i, L, l - 1, -1});
        while (L < l) q[i].res += f[L - 1] + !k, L ++ ;
        if (L > l) range[R].push_back({i, l, L - 1, 1});
        while (L > l) q[i].res -= f[L - 2] + !k, L -- ;
    }

    memset(g, 0, sizeof g);
    for (int i = 1; i <= n; i ++ )
    {
        for (auto y: nums) ++ g[w[i] ^ y];
        for (auto& rg: range[i])
        {
            int id = rg.id, l = rg.l, r = rg.r, t = rg.t;
            for (int x = l; x <= r; x ++ )
                q[id].res += g[w[x]] * t;
        }
    }

    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 ++ ) printf("%lld\n", ans[i]);

    return 0;
}

1. 读取序列长度n、询问数量m和整数k，读取序列的元素。
2. 预处理出所有二进制表示下(1)的个数为k的数，存入nums向量。然后遍历序列，计算g数组（记录与满足条件的数异或后的计数）和f数组（为后续计算做准备）。
3. 读取每个询问的区间，将询问信息存储到q数组中。
4. 计算分块的长度len，对询问按照cmp函数定义的规则进行排序。
5. 处理询问：
   • 使用双指针L和R，根据指针与询问区间端点的关系，记录区间的增减信息到range数组中，并更新当前询问的部分答案res。
   • 遍历序列，重新计算g数组，根据range数组中的信息，进一步更新每个询问的答案res。
6. 对相邻询问的答案进行累加（二次离线的关键步骤），将答案存入ans数组并输出。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 初始化操作：预处理满足条件的数、计算g和f数组，时间复杂度为(O(n + 2^{14}))。
• 排序操作：对询问进行排序，时间复杂度为(O(m\log m))。
• 处理询问操作：双指针移动和二次处理区间增减信息，时间复杂度为(O(n + m\sqrt{n}))。
• 总的时间复杂度为(O(n + 2^{14}+ m\log m + n + m\sqrt{n}))，由于(2^{14})是常数，近似为(O(m\sqrt{n}))（当n和m规模相近时）。

（二）空间复杂度

需要存储序列元素w[N]、询问信息q[N]、区间增减信息range[N]、辅助数组f[N]和g[N]以及答案数组ans[N]等，空间复杂度为(O(N + N + N\times N + N + N + N)=O(N^2)) ，但实际有效占用空间主要为(O(N)) 。