CST PA3

3-1 Build

算法构思

采用 node 类存储每个节点对应的信息.

// Line 23
class node {
public:
    int parent;     // 父亲编号
    int firstchild; // 长子编号
    int lastchild;  // 幼子编号
    int pred;       // 左兄弟编号
    int succ;       // 右兄弟编号
    int size;       // 子树大小
    int height;     // 子树高度
    int suffix;     // 自身及后缀兄弟结点最大高度
    node(): parent(0), firstchild(0), lastchild(0), pred(0), succ(0), size(0), suffix(0), height(0) {}
} *tree;

根节点编号为 1, 所有节点信息默认初始化为 0, 表示相应信息不存在. 其中 suffix 维护了节点本身及其靠后兄弟 height 的最大值, 在每次进行子树移动时, 只需要向前向上维护 size, suffix 并且更新 height 即可, 如此操作可将时间消耗控制在 cost 内.

void Init()

首先调用 Init(n) 对多叉树的 parent, firstchild, lastchild, pred, succ 进行初始化.

void InitTree()

随后 Init(n) 调用 InitTree(1), 借助辅助栈 stack 使用后序遍历的迭代情形对多叉树的 size, height, suffix 进行初始化. 类似二叉树的后续遍历, 对于一个节点, 我们首先初始化其 lastchild 直到 firstchild, 最后初始化其本身.

void InitNode()

// Line 36
void InitNode(int x) {
    if (x == 0) return;
    if (tree[x].firstchild == 0) { // 叶节点.
        tree[x].size = 1;
        tree[x].height = 0;
        tree[x].suffix = tree[tree[x].succ].suffix;
    }
    else { // 子树根节点.
        int child = tree[x].lastchild;
        while (child) {
            tree[x].size += tree[child].size;
            child = tree[child].pred;
        }
        tree[x].size += 1;
        tree[x].height = tree[tree[x].firstchild].suffix + 1;
        tree[x].suffix = max(tree[x].height, tree[tree[x].succ].suffix);
    }
}

对于叶子节点, 将其 size 设置为 1, height 设置为 0, suffix 设置为其右兄的 suffix (若右兄不存在, 即编号为 0, 那么会返回 tree[0].suffix, 即 0).

对于一个子树根节点, 将其 size 设置为其子节点的 size 和加 1, height 设置为长子节点的 suffix 加 1, suffix 设置为其自身高度与右兄 suffix 的最大值 (若右兄不存在, 即编号为 0, 那么会返回 tree[0].suffix, 即 0).

int Readnode()

Readnode() 读入一条路径, 并返回这条路径上的最后一个合法节点编号, real_node 表示当前已读入路径对应的合法节点, tmp_node 表示读入下一个座位后节点的状态, 若为 0, 说明已经进入了无效路径, 直接将之后路径截断即可 (即只读入数据而不对 real_node 进行更新).

void Update()

对于每次删除和插入子树, 要在操作位置进行 size, height, suffix 的更新. 其中 height, suffix 的更新比较一致, 将其写作接口 Update().

// Line 102
void Update(int tmp) {
    while (tmp) {
        // 更新 suffix.
        tree[tmp].suffix = max(tree[tmp].height, tree[tree[tmp].succ].suffix);
        while (tree[tmp].pred) {
            tmp = tree[tmp].pred;
            tree[tmp].suffix = max(tree[tmp].height, tree[tree[tmp].succ].suffix);
        }
        // 更新 height.
        tmp = tree[tmp].parent;
        if (tmp == 0) return;
        tree[tmp].height = tree[tree[tmp].firstchild].suffix + 1;
    }
}

由于 suffix 存储的是节点本身及其后缀兄弟节点的最大 height, 因此对于修改过的节点, 只需要顺次更新其前缀兄弟的 suffix, 当自身已是长子节点时, 更新其父亲的 height 与 suffix, 并以其父亲节点为基准继续更新前缀节点.

void Remove()

对于要删去的节点 remove_node, 首先特判其左右兄弟的存在性, 若都存在则将其左兄弟的右兄设置为其右兄弟, 其右兄弟的左兄设置为其左兄弟. 否则 remove_node 必然是其父节点的长子节点或幼子节点, 只需相应进行更新. 最后将 remove_node 的左右兄弟及父亲置为 0 即可.

随后对全树进行更新. 更新 size 只需沿着 remove_node 的父节点向上, 逐次减去 tree[remove_node].size 即可. 接着更新 height 与 suffix, 若 remove_node 的左兄存在, 直接对其进行 Update() 即可; 否则转到 tree[remove_node].parent, 更新其 height, 并进行 Update().

void Insert()

对于插入的父节点 attach_node, 源子树节点 insert_node, 插入位置 rank, 首先设置 insert_node 父亲为 attach_node. 若父节点无子节点, 则设置 firstchild, lastchild 均为 insert_node. 否则特判插入位置是否为 firstchild 或 lastchild 节点, 并相应进行更新, 原理同 Remove().

随后对全树进行更新. 更新 size 只需沿着 insert_node 的父节点向上, 逐次加上 tree[insert_node].size 即可. 接着更新 height 与 suffix, 直接从 insert_node 开始进行 Update().

void Input()

直接读取操作序列并进行操作即可.

问题解决

由于数据规模 N 为 1, 1e6, 在初始化时若采用后序遍历的递归版本, 会导致爆栈 (事实上, 我自行构造了一条单链的特殊情况, 在这种情况下, 程序不会正常返回), 因此采用了后序遍历的迭代版本.
初始化叶节点时, 原本进行了 tree[x].suffix = 0, 事实上需要修改为 tree[x].suffix = tree[tree[x].succ].suffix, 因为叶节点右边的兄弟的高度未必为 0.
在 Remove() 中更新父节点的高度时, 需要特判父节点是否无子节点.

...
// Line 143
tmp = parent;
if (tree[tmp].firstchild == 0) tree[tmp].height = 0;
else tree[tmp].height = tree[tree[tmp].firstchild].suffix + 1;
...

在进行子树移动操作时, 需要在读入 remove_node 后立刻进行 Remove() 操作, 随后进行读入 attach_node 并进行 Insert() 操作. 否则若读入 remove_node 后紧接读入 attach_node, 会导致没有更新删除节点而产生读入错误, 导致进入死循环, 产生 TLE 错误.

复杂度估计

时间复杂度

InitTree() 过程仅仅与全树节点数目有关系, 每一个节点入栈、出栈、初始化各一次, 时间复杂度为 $O(n)$;

Remove() 与 Insert() 过程中, 在寻找相应节点的时间复杂度为 $O(cost)$, 更新 size 只与树深有关, 更新 height 和 suffix d等价于反向的查找过程, 时间复杂度为 $O(cost)$;

子树查询仅消耗访问内存常数时间, 时间复杂度为 $O(m)$.

综上, 算法总时间复杂度为 $O(n + cost + m)$.

空间复杂度

算法空间复杂度主要来自读取并存储数据的过程:

每个 node 类对象都存储了常数个成员, 消耗常数空间, 总体空间消耗为 $O(n)$.

...
// Line 23
class node {
public:
    int parent;
    int firstchild;
    int lastchild;
    int pred;
    int succ;
    int size;
    int height;
    int suffix;
    node(): parent(0), firstchild(0), lastchild(0), pred(0), succ(0), size(0), suffix(0), height(0) {}
} *tree;
...
// Line 192
tree = new node[n + 2];
...