ABC283 G

Raisetsu41 · 2022-12-25 16:46:25 · 题解

其实比较容易看出是线性基模板题。
那就讲讲线性基与其扩展。

\mathbb{Definition}

现有一正整数集 S ，关于 S 构造的线性基可以视为另一个集合，且满足以下性质

• 可以通过线性基中子集的异或值得到 S 中所有子集的异或值，且线性基的元素个数在满足条件的情况下最小
• 线性基中子集异或值不存在 0
• 线性基中不同子集的异或值不同
• 线性基中不同元素的二进制最高位互不相同

不严谨的一句话概述：线性基与原集合在关于异或的问题上等价，且元素个数小于原集合。

\mathbb{Build}

首先令线性基元素集合为 Base 。

\mathbb{Insert}

在插入某个数 val 时，从二进制最高位往最低位扫。

在第 i 位有值的情况下，若 base_i 不存在，就 base_i := val，否则 val \otimes base_i 。

void insert (LL val) {
    for (int i = BIT; i >= 0; i--) {
        if ((1ll << i) & val) {
            if (base[i] == 0) {
                base[i] = val;;
                break;
            } else val ^= base[i];
        }
    }
}

\mathbb{Min/Max \ Query}

贪心思想

LL query_min() {
    for (int i = 0; i <= BIT; i++) if (base[i]) return base[i];
    return 0;
}
LL query_max() {
    LL res = 0;
    for (int i = BIT; i >= 0; i--) if ((res ^ base[i]) > res) res ^= base[i];
    return res;
}

\mathbb{Kth \ query}

首先对线性基进行改造，使得线性基的每一位都相互独立。
目标是在改造后使得二进制的每一位 i 上，除了 base_i 是 1 其他的均为 0 。
具体来说，从高往低扫，如果存在 i < j ，且 a_j 的第 i 位是 1，就将 a_j 异或上 a_i。
查询就是二进制拆分。

void rebuild() {
    for (int i = BIT; i >= 0; i--)
        for (int j = i - 1; j >= 0; j--) if (base[i] & (1ll << j))
            base[i] ^= base[j];
    for (int i = 0; i <= BIT; i++) if (base[i]) p[cnt++] = base[i];
}
int querykth(int k) {
    int res = 0;
    if (k >= (1ll << cnt)) return 0x3f3f3f3f;
    for (int i = BIT; i >= 0; i--) if (k & (1ll << i)) {
        res ^= p[i];
    }
    return res;
}