CF241B 题解

· · 题解

P5283 [十二省联考 2019] 异或粽子 加强版。

step1

首先先将 m 乘二，变成统计最大的 m 个有序对。

把所有 a_i 插入到一个 Trie 中，对于每个结点记录子树中叶子个数，第一步先来考虑求出第 m 大值是什么，记第 m 大值为 lim。

这个可以从高位到低位按位确定。假设当前考虑完了 [30,b+1] 位，正在确定第 b 位，对于 Trie 上第 b+1 层的每一个结点 i，记录另一个结点 cor_i 表示 i 和 cor_i 对应值的异或和的 [30,b+1] 位等于 lim。这样就能对于第 b 位统计出满足异或和 [30,b+1] 位和 lim 相等且第 b 位为 1 的点对数，从而确定 lim 的第 b 位是 0 还是 1。

由于 Trie 上每个结点只会被遍历一遍，这部分复杂度是 O(n \log V) 的。

step2

接下来考虑统计答案，这里只统计异或和小于 lim 的点对贡献，等于 lim 的贡献为 lim*(m-cnt)，cnt 为异或和小于 lim 的点对数。

枚举点对异或和和第 m 大值二进制表示的 lcp。具体来讲，依然枚举 Trie 树上的一个点 i，贡献其实就是 i 的子树 t 以及 cor_i 的子树 t \oplus 1 中任意两对值的异或和，异或和没有很好的性质，只能拆位算，记 s_{i,j,0/1} 表示 i 的子树中第 j 位为 0/1 的值的个数，然后直接枚举每一位算贡献即可。

step3

最后来分析复杂度：

首先是 s_{i,j,0/1} 的计算，如果点 i 两个儿子都有，那么直接 O(\log V) 暴力合并，否则 s_{i} 可以直接继承其仅有的一个儿子的值（可以用指针实现），这样在三度点处的贡献是 O(\log V) 的，在二度点处为 O(1)，由于叶子个数只有 O(n) 个，所以三度点也只有 O(n) 个，于是这部分是 O(n \log V) 的。

然后是暴力拆位算贡献的部分，每一对 (i,cor_i) 会造成 O(\log V) 的贡献。如果 i,cor_i 中有一个是三度点，注意到 i 和 cor_i 是一一对应的，所以这样的 (i,cor_i) 只有 O(n) 个；注意到如果 i 和 cor_i 中如果有一个是空子树，那么是不需要贡献 O(\log V) 的，而如果 i,cor_i 均为二度点且有 O(\log V) 的贡献的话，那么是必然不会继续从 i 递归到它的子树中的，所以对于每一个叶子，其祖先中的二度点至多有 1 个会有贡献，因此这样的二度点总数也是 O(n) 的，于是这部分复杂度也是 O(n \log V) 的。

总复杂度 O(n \log V)。

代码（写的很丑QwQ）：

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define rep for (int t = 2; t--; )
using namespace std;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x;
}

typedef long long ll;
const int N = 5e4+5;
const int Mod = 1e9+7;

int n, a[N], tot = 1, ans;
ll m, lim;
int bf[N * 2][2][30], c, (*s[N * 30])[30];
int cor[N * 30];
vector<int> id[31];

inline void Add(int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

struct node {
    int son[2], siz, d;
} T[N * 30];

#define son(p, s) T[p].son[s]

inline void ins(int v) {
    int p = 1;
    for (int i = 29; ~i; i--) {
        int g = v >> i & 1;
        if (son(p, g)) p = son(p, g);
        else p = son(p, g) = ++tot, T[p].d = i, id[i].pb(p);
        T[p].siz++;
    }
    if (T[p].siz == 1) s[p] = bf[c++];
}

int main() {
    n = read(), m = read() * 2ll; T[1].d = 30;
    for (int i = 1; i <= n; i++) ins(read());

    for (int i = tot; i; i--) {
        rep if (son(i, t)) s[son(i, t)][t][T[son(i, t)].d] += T[son(i, t)].siz;

        if (son(i, 0) && son(i, 1)) {
            s[i] = bf[c++];
            for (int k = T[i].d - 1; ~k; k--)
                rep s[i][t][k] = s[son(i, 0)][t][k] + s[son(i, 1)][t][k];
        } else if (son(i, 0) | son(i, 1)) s[i] = s[son(i, 0) | son(i, 1)];
    }

    id[30].pb(1); cor[1] = 1;
    for (int b = 29; ~b; b--) {
        ll cnt = 0;
        for (int i : id[b + 1]) if (cor[i])
            rep cnt += T[son(i, t)].siz * T[son(cor[i], t ^ 1)].siz;

        if (cnt >= m) {//这一位为1
            lim |= 1 << b;
            for (int i : id[b + 1])
                rep cor[son(i, t)] = son(cor[i], t ^ 1);
        } else {//这一位为0
            m -= cnt;
            for (int i : id[b + 1])
                rep {
                    cor[son(i, t)] = son(cor[i], t);
                    int x = son(cor[i], t ^ 1), y = son(i, t);
                    if (x && y) {
                        Add(ans, lim * T[x].siz * T[y].siz % Mod);
                        for (int k = b; ~k; k--)
                            rep Add(ans, (1ll << k) * s[x][t][k] * s[y][t ^ 1][k] % Mod);
                    }
                }
        }
    }

    Add(ans, lim * m % Mod);

    printf("%lld", (ll) ans * (Mod + 1) / 2 % Mod);
    return 0;
}