Circuit

CST PA4

4-1 Circuit

算法构思

数据结构

本题需使用 Trie Tree 数据结构, 关于 Trie Tree 的介绍可参考此篇文章. 因为涉及的字符仅为 0, 1, 因此实质上相当于一棵 Binary Tree.

// Line 7
ull str[500500];
int ans[500500];

使用 unsigned long long str[] 数组储存 01 串, 不断更改当前的查询串编号, 将超出区间的串从 Trie Tree 中删去, 进入区间的串添加到 Trie Tree 中, 得到的结果存储在 int ans[] 中.

// Line 14
class node {
public:
    int son[2] = {0};
    int cnt = 0;
} trie[32001000];

因此 Trie Tree 中的串至多为 500000 个, Trie Tree 中的节点至多为 500000 * 64 = 32000000 个. 在节点内部维护其左右子节点 son[0], son[1], 并记录经过该节点的 01 串数 cnt.

void ReadAll()

使用 getchar() 逐字符读入所给串, 计算其二进制值并存储为 unsigned long long.

void Insert()

定义全局变量 pointer 记录下一个将被利用的节点编号.

对于一个 unsigned long long 存储的 01 串, 从根节点 trie[0] 开始从高到低逐位读取其各位数值, 为 0 则转向当前节点左孩子, 为 1 则转向当前节点右孩子. 若子节点存在, 则相应 cnt++; 若子节点为空, 则用 trie[pointer] 对其初始化, 并 cnt++.

当读入 01 串最后一位, 到达叶节点时, 直接将对应 01 串的编号存储在叶节点的 cnt 中.

void Remove()

对于一个 unsigned long long 存储的 01 串, 按照同样过程在 Trie Tree 中访问其各个节点, 对应 cnt--. 若 cnt 减少到 0, 直接将其父节点的子节点标记置为 0, 以该节点为根的子树在之后都不会被访问.

int Query()

为了获得最大异或和, 在树上的每一步向下移动都尝试向着与所给串相反的方向进行即可.

问题解决

• 按照编号从下往上扫描序列, 向 Trie Tree 中插入字符串, 靠前字符串编号会覆盖靠后字符串编号, 查询时即可输出最靠前序列编号.
• 特别地, 若所有 01 串均相同, 那么 Trie Tree 退化为一条单链. 此时唯一叶节点会在最后被串 0 标记覆盖, Query(0) 返回 0, 只需将其单独改为 1 即可.

复杂度估计

时间复杂度

对每个 01 串进行 Insert, Remove, Query 的时间复杂度均为 $O(1)$, 而每个串至多进行 Insert, Remove, Query 各一次.

综上, 算法总体时间复杂度为 $O(64n)$.

空间复杂度

插入的串至多产生64n个节点，而每个节点只维护了左节点、右节点、经过次数（叶节点单位值）这三个信息，因此空间复杂度为O(64n)，常数上限为3倍。

其他数组均为500050大小，相对花销较小。

本体空间复杂度取决于 01串数 n, 最多在 Trie Tree 中产生 $64n$ 个节点. 题解中使用 trie[], str[] 与 ans[] 数组模拟了一棵 Trie Tree, 最坏情况下整体需要的空间为 $O(64n)$.

本题中直接开辟了相关大小的数组存储信息,

...
// Line 7
ull str[500500];
int ans[500500];
...
// Line 14
class node {
public:
    int son[2] = {0};
    int cnt = 0;
} trie[32001000];
...

空间消耗最坏情况约为: $5\times 10^5 \times 8B + 5\times 10^5 \times 4B + 3.2\times 10^7 \times 12B = 372MB < 512MB$, 符合题目要求范围.