Kevin's blog

DSA PA3 Report

PA3-1 Build解题报告

算法构思与实现要点

本题主要任务在于维护一个多叉树，根据邻接表结构初始化，根据父子层次关系实现删除、插入子树操作，并在操作过程中维护节点高度和子树规模信息，便于查询。具体而言，每个节点是一个Node结构类型的指针，维护的信息包括：

height 子树高度，初始（指单节点时）为0
size 子树规模，初始为1
childnum 孩子节点数量，输入给出
suffixMaxHeight 同级后续兄弟（包括自己）的最大高度，避免在高度更新时遍历孩子节点，初始为0
parent 指向父节点（根节点为nullptr）
firstChild 指向长子节点（叶子节点为nullptr）
prevSibling 指向前一个兄弟节点
nextSibling 指向后一个兄弟节点

可以看出，多个兄弟子节点之间通过双向链表结构维护，便于正向根据rank查询特定子节点以及反向更新高度信息；父子关系通过长子firstChild和parent维护，便于沿祖先路径反向更新子树规模信息。

本题中，首先根据给出的子节点的邻接表结构初始化各节点的父子、兄弟关系（节点与编号的对应关系通过一个数组维护），然后按照BFS的顺序从上到下（从根到叶）、从左到右（从长子到末子）的顺序将所有节点压入临时数组中，沿逆向初始化size、height和suffixMaxHeight，具体而言，每弹出一个节点cur（非根节点），将对其父节点和直接长兄（若没有则为父节点）的上述信息更新：

$$ \mathrm{cur\to parent\to size += cur\to size} $$
非长子：$$ \mathrm{cur\to prevSibling\to suffixMaxHeight = \max{cur\to prevSibling\to height, cur\to suffixMaxHeight}} $$
长子：$$ \mathrm{cur\to parent\to height = cur\to suffixMaxHeight + 1} \
\mathrm{cur\to parent\to suffixMaxHeight = cur\to parent\to height} $$

由归纳法不难证明这样初始化的正确性：最先被弹出的“右下方”叶子节点已经被正确初始化（如上列出），假设前$k$个弹出的节点都已经被正确初始化，第$k+1$个弹出的节点的size、height和suffixMaxHeight只取决于右侧兄弟节点和下方节点，由于逆向的方向保证，这些节点一定已经先被弹出，利用它们的这三个信息更新得到的第$k+1$个节点信息也是正确的。

此后的每次子树移动操作，包括一次节点删除操作和插入操作，根据给定路径从根节点出发找到对应节点后（其中，如果遇到某一层指定的子节点rank大于等于该节点的childnum就及时终止），改变局部节点连接关系，并相应更新节点存储的信息即可。具体而言，沿着直系祖先路径向上递归更新子树规模，沿着先向左再向上的路径，递归更新自己及所有长兄的和祖先节点的suffixMaxHeight和height，其他节点均不受局部删添的影响。

对于每次查询操作，直接找到对应节点输出其保存的height或size信息即可。

完成过程中遇到的问题与解决过程

在调整局部连接关系的时候务必格外细心，注意每个需要更新的信息都要更新到，包括父节点的childnum、父子的连接关系、前后相邻兄弟节点的连接关系等，开始因为信息某些条件下的信息遗漏带来了漫长的debug。
开始初始化操作是在每次一个节点上插入孩子节点时都进行一次节点信息更新，这样时间复杂度将达到$O(n^2)$量级，在某些极端情况下（如每个节点子节点数目都很少，甚至连成一条链）时会超时。调整为全部连接关系处理完成后一次性初始化节点信息，就能保证在$O(n)$复杂度内完成信息初始化。
初始化时也要注意信息初始化完整，开始遗漏对长子处父节点suffixMaxHeight的初始化也会导致错误。

复杂度估算

时间复杂度：
1. 初始化：新建节点、初始化连接关系、遍历节点压入临时数组、逆向逐一弹出节点更新父节点/直接长兄节点信息这四大操作均与节点数量线性正比，故为$O(n)$。
2. 子树移动：主要时间消耗来自两次根据指定路径寻找节点、两次沿指定路径反向更新suffixMaxHeight和height，这两项操作均与题目定义的$cost$线性正比，以及两次沿直系祖先路径更新size，其在最坏情况下也将达到$cost$。至于局部连接关系调整可以在$O(1)$内完成。
3. 查询：主要时间消耗来自沿路径找到相应节点，也与$cost$线性正比。综上，2、3两项操作消耗的总时间为$O(cost)$，这里$cost$为题目定义所有操作$cost$的总和，$cost \le 10^6$。
4. 综上，该算法时间复杂度为$O(n+cost)$，其中通过后缀最大高度信息的维护避免了在访问每个节点时遍历所有节点，直接通过长子一步更新高度信息，是保证所有操作总数时间复杂度维持在$O(cost)$的关键。这一用节点信息维护区间信息的思想非常值得后续借鉴。
空间复杂度：主要空间消耗来自两次分别根据编号和BFS遍历次序暂存结点指针，故空间复杂度为$O(n)$。

PA3-2 NotFound解题报告

算法构思与实现要点

本题主要的限制在存储的空间上，如果直接用char数组仅仅存储输入字符串最坏情况下就已经需要约17MB，因此采用bitmap方式对输入字符串以及后续用于标记已有子串的bool数组进行压位存储，每个0/1只占用1个bit内存，总体内存开销大约能减小到用char/bool数组时的1/8。具体算法实现主要分为以下几个部分：

读入$A$：将输入的01串$A$存入一个unsigned long long数组中，使用getchar()读入，每64位为一个单位作为一个unsigned long long型数据存入数组；
枚举子串长度$k$（代码中使用的字母是$i$）：注意到，长度为$k$的不同01串共有$2^k$种，而一个长度为$n$的01串最多包含$n-k+1$种长度为$k$的不同01串，要求长度为$n$的01串能包含所有长度为$k$的子串，要求：$$ n-k+1>2^k $$ 本题中$n \le 16777216=2^{24}$，由单调性和零点存在定理易得$k \le 23$ ，也就是说本题答案长度一定不超过$min{23, n}$，因此可以考虑直接从小到大枚举答案子串长度；
枚举$A$中所有长度为$k$的子串（先读入第一个，然后通过左移、取模、读入下一位依次读取后续子串），将出现的子串当作一个二进制数，作为下标标记在found数组中（同样是bitmap方式存储），同时用一个整数flag记录当前长度为$k$的子串中没有被标记的最小01串，如果flag >= (1 << k)说明长度为$k$的所有子串都已被包含，直接进入下一循环；否则将找到的flag用k位二进制表示（高位补0）输出即为答案。

注：用unsigned long long实现bitmap主要包含两个函数：int get(ull bitmap[], int k)获取bitmap中k号bit的值（0/1），void set(ull bitmap[], int k)将bitmap中k号bit的值置1，具体实现方式部分参考讲义（将8位char数组改为了64位unsigned long long数组，通过右移后按位1实现get，与讲义上的test略有不同）。

完成过程中遇到的问题与解决过程

依次枚举$A$中所有长度为$k$的子串时，最初实现时在左移后漏掉了对$(2^k-1)$取模去掉最高位（潜意识里认为左移后最高位就溢出了，以后在想象整数的位存储表示时不要忘了包含高位前导0）。
最初在输出答案时是直接输出整数flag的二进制表示，忽略了位长要求，即在本题中000和0是不同的情况。
两个问题均通过构造简单测例发现问题、输出中间结果和vscode断点调试解决。

复杂度估算

时间复杂度：设输入01串长度为$n(\le 2^{24})$，读入过程时间复杂度为$O(n)$，记$k=min{23, n}$（一般地，事实上$k$约为$\log n$，但鉴于本题中常数不大采取简化实现），get、set操作均为$O(1)$复杂度，两层枚举复杂度为$O(nk)$，此外还有flag在found数组下标中的移动占用时间$O(2^1+…+2^k)=O(2^{k+1})$，最坏情况下，估计操作总数$2^{24}+232^{24}+2^{25} < 322^{24} = 2^{29} \approx 0.5 * 10^9$，不会超时。
空间复杂度：主要空间开销在于存储输入01串和维护标记数组，采用bitmap方式压位存储空间复杂度为$O(2*n/8)$，实际最大空间开销约为$2 * \frac{2^{24}}{8}$B $\approx 4$MB $< 6$MB，不会超出空间限制。

PA3-4 Kidd解题报告

算法构思与实现要点

本题主要任务是维护一棵线段树，实现区间更新与区间查询操作。

由于本题区间总长度 $n$ 上界过大，直接对 $[0, n]$ 区间用二分划分方式构建线段树带来的空间成本（包括时间成本）过高，因此首先需要进行区间离散化。具体而言，首先读入并在数组 $a$ 存储待查询的区间端点（共 $2m$ 个数，题目原来给的是每个区间的左闭右闭表示，读入后首先将右端点 $+1$ 改为左闭右开形式存储，方便后续操作在区间端点处不会重复记录），排序、去重后建立与数组下标的一一映射，线段树的节点只需存储数组下标，通过 $a$ 数组映射即可得到真实数据。

线段树中的每个节点维护一段区间的信息，具体而言包括：

区间左右端点对应的数组下标 $l, r$（左闭右开，对应区间 $[a[l], a[r])$ ）
$[a[l], a[r])$区段内的所有翻转次数和 $sum$
该节点被懒惰标记（标记覆盖全域、不再下传）的次数 $cnt$
节点左右孩子地址 $lc, rc$（没有则为空指针）

线段树中只需维护一个根节点$root$，即可通过内部节点指向关系维护树结构。此外，线段树还需要实现两个操作：

区间更新：从根节点出发递归更新 $[a[l], a[r])$ 覆盖到的节点的 $sum$ 值，对所标记区间被完全覆盖的节点懒惰标记 $cnt$ 加一，不再下传。
区间查询：对 $[a[l], a[r])$ 完全覆盖的节点的 $sum$ 值求和，必要时需要将懒惰标记下放。

具体细节可参见下列伪代码：

// 区间更新
void insert_at(node, i, j) {
  l, r = node->l, node->r;
  if ([i, j)交[l, r)为空)
    return;
  if ([l, r)含于[i, j)) {
    更新当前节点的 sum (+=a[r]-a[l]) 和 cnt (+=1);
    return;
  }
  根据相交情况（l, r, i, j大小关系）更新当前节点 sum;

  // 递归下移
  mid = (l + r) / 2;
  if ([i, j)与[l, mid)有交) 
    递归更新左孩子;
  if ([i, j)与[mid, j)有交)
    递归更新右孩子;
}

// 区间查询
long long query_at(node, i, j) {
  l, r = node->l, node->r;
  if ([i, j)交[l, r)为空) {
      return 0;
  }
  //递归基：找到了[i, j)在区间划分中的一个覆盖块，返回该块记录的sum值，停止下探
  if ([l, r)含于[i, j)) {
      return node->sum;
  }
  //未完全覆盖但有相交，需要将懒惰标记下放
  ans = 0;
  mid = (l + r) / 2;
  左孩子：sum += (a[mid] - a[l]) * node->cnt; cnt += node->cnt;
  右孩子：sum += (a[r] - a[mid]) * node->cnt; cnt += node->cnt;
  if ([i, j)与[l, mid)有交) 
    ans += query_at(node->lc, i, j);
  if ([i, j)与[mid, j)有交)
    ans += query_at(node->rc, i, j);
  node->cnt = 0;
  return ans;
}

完成过程中遇到的问题与解决过程

scanf读入单字符的坑点：%c会接受转义字符，包括回车！在%c前加空格可过滤回车。
双指针去重时，可能在最后连续重复而踩出界，务必及时退出！
必须使用懒惰标记延迟下放才能保证查询时能在覆盖块处及时终止，停止下探，否则必须探到叶节点来做更新，一次查询即耗费最坏约$O(2·2m)$时间，必将TLE。
注意下放时是把懒惰标记整个都删除了的，要下放两边都要一起下放！

有许多问题是通过vscode调试以及对拍解决的。

复杂度估算

时间复杂度：
1. 读入、排序、去重区间端点值：$O(3m + 2m\log 2m + 2m)$
2. 每次查询前根据端点值($a[l], a[r]$)确定对应数组下标($l,r$)，需要进行两次二分查找，总共花费时间：$O(2m\log 2m)$
3. 对每次区间更新或查询操作，在线段树的每一层至多访问（更新/查询$sum$值）四个节点（因为区间是连续的，在访问到某层时至多被分成两个连续的区间段，若涉及五个节点，其中必定有三个节点表示的区间段是连续的，且三个中至少完整覆盖两个区间，这两个区间的并就被完整覆盖，又由于左右二分的递归访问模式，这两个节点的公共父节点就已经被完全覆盖，不会再下传）。线段树是有$2m$个节点的完全二叉树，树高为$O(\log 2m)$，故每次访问最坏情况下时间复杂度约为$O(4\log 2m)$，总共时间开销约为：$O(4m\log 2m)$
4. 综上，总时间复杂度估算为$O(5m+8m\log 2m)$，记$\tilde{m}=2m$，渐进估算为$O(\tilde{m}\log \tilde{m})$
空间复杂度：
线段树存储的总区间长度至多为$2m$，需要约$4m$个节点，故空间复杂度为$O(4m)$。

PA3-6 Nearest Neighbor解题报告

算法构思与实现要点

本题主要任务时维护一棵kd树，分块式存储 $d$ 维空间中 $n$ 个点的位置和位置关系，实现给定点最近邻的快速查询。

首先将 $n$ 个点的坐标读入数组 $p$ 中存储，每个点唯一对应一个数组下标。kd树的中内部节点负责记录空间划分相关信息，叶子节点负责集中记录这块空间内的点。为了减小树高同时充分利用缓存优化程序效率，每个叶子节点负责记录在数组中连续分布的约 $N$ (实践中取20较合适) 个坐标点。

具体而言，内部节点需要存储：

在该节点上的划分维度 $r \ (0 <= r < d)$
将左右孩子中的点划分开的分界线界桩 $marker$（即该节点下属包含的所有坐标点在第 $r$ 维的中位数）
左右孩子地址 $lc, rc$

为了方便统一节点数据类型，叶子节点继承了普通节点，但它主要需要存储的是：

该叶子节点记录的区域在数组 $p$ 中开始、结尾的位置 $start, end$（左开右闭）

读入数据后，首先要根据所给点坐标建树：从根节点 $root$ 出发，从第 $0$ 维开始，相继以第 $r$ 维作分界线划分数组 $p$ 中 $[start, end)$ 的坐标点。当该层节点数 $\le N$ 时，直接建立叶子节点存储 $start, end$ 并返回。否则，将 $[start, end)$ 内的坐标点按第 $r$ 维从小到大排序，得到中间坐标点数组下标 $mid = (start + end) / 2$，记录分界界桩值（$p[mid]$的第$r$维），然后交给左右孩子分别在第 $(r + 1) % d$ 维度划分 $[start, mid)$ 和 $[mid, end)$ 内的坐标点，直到该层节点数 $\le N$ 。

接着就是查询每个询问点到最近邻的距离。具体而言，遵循以下步骤：

在递归查找中传递一个公共变量curMinDist，维护当前搜索到的最近邻距离平方值，初始设为无穷大（大于最大可能值）；
根据各个内部节点维护的划分信息，找到询问点所在的分区，在随机情况下，该分区内的坐标点离询问点距离近的概率较大，找到对应叶子节点后暴力搜索该分区内的最近邻，更新curMinDist；
递归回溯到上一层节点，计算到分界界桩的距离平方，若大于等于当前维护的curMinDist，则分界线另一侧所有坐标点都不可能是最近邻（至少不是唯一的），即可剪去对另一分支的搜索；否则仍需下探搜索另一侧，并且在每一层都首先执行上述判定剪去不必要的搜索；
以此类推，不断向上层递归回溯，最终记录的curMinDist即为整体的最近邻距离平方值。

完成过程中遇到的问题与解决过程

局部变量一定要初始化！初始化为0不可省！
快排模板要背熟！细节要理解处理清除（以上两个问题通过vscode调试观察中间变量值找出并解决）
在搜索到某一层节点时，若询问点到分界界桩的距离平方大于等于当前维护的curMinDist，只能保证在分界线的另一侧不可能有更小的距离值，不能保证在询问点所在这一侧没有！（该问题通过在小数据范围内与蛮力遍历算法对拍找出，通过分析错误样例找到问题所在并解决）

复杂度估算

时间复杂度：
1. 建树过程：kd树是一棵完全二叉树，$n$ 个坐标点大约划分为 $n/N$ 个叶子节点存储，故树高估算为 $O(\log \frac{n}{N})$；在深度 $h$ 层需要对长为 $n / 2^h$ 的序列进行共计 $2^h$ 次快速排序，则总共的时间开销为：$O(\sum\limits_{h=1}^{\log\frac{n}{N}} 2^h·\frac{n}{2^h}\log\frac{n}{2^h}) = O(\frac{n}{2}\log\frac{n}{N}\log nN)$，渐进复杂度为$O(n\log^2 n)$
2. 查询过程：每次查询最好情况为一次查到：$O(\log\frac{n}{N} + N)$，最坏情况为全部遍历$O(2\frac{n}{N} + n)$，在$n \gg d$ 且数据均匀随机分布的情况下，平均而言在最近邻就分布在问询点所在分区最近的几个叶子节点处，故 $q$ 次查询总的平均渐进时间复杂度为 $O(q(\log\frac{n}{N} + N))$
空间复杂度：主要空间开销包括在数组中存储 $n$ 个 $d$ 维点的坐标以及kd树中存储约 $2n/N$ 个节点，渐进复杂度为 $O(n)$。