NGC5457's Site

分类： 算法

  • 维护树上编号连续节点构成连通块/虚树的一种方法

    维护连通块

    现有一棵 $n$ 个节点的树。我们构建一最小的连通块 $S(l,r)$，包含编号在 $[l,r]$ 中的所有节点。多次询问，每次对于任意一对 $[l,r]$，询问关于这连通块的信息。

    如果可以离线/可持久化，此类问题有一通用思路：用扫描线维护“$r$ 固定时不同 $l$ 构成连通块的信息”。若 $[p,q]\subseteq[l,r]$，则 $S(l,r)\supseteq S(p,q)$；对于一固定的 $r$，我们维护 $l$ 分别取 $r,r-1,\cdots,1$（向左拓展）时，连通块的增量。对于点 $x$，我们记录 $t_r(x)$ 表示 $r$ 固定时使得 $x\in S(l,r)$ 的最大的 $l$。假设已经对于 $r$ 维护好了；现在拓展到 $r’=r+1$。

    若 $x\notin \{r,r+1\}$，则 $t_{r+1}(x)\neq t_{r}(x)$ 是

    • $x$ 在 $r$ 到 $r+1$ 的简单路径上，且
    • $t_{r+1}(x)=r$

    的充分必要条件。

    考虑任意 $l$。由于 $S$ 是极小的，故将 $r+1$“加入”$S(l,r)$ 得到 $S(l,r+1)$，只需找到 $r+1$ 和连通块在树上最接近节点之间的路径，将路径上所有点加入连通块；由树的性质，此路径是通向 $[l,r]$ 中任意节点的必经之路，也即 $r,r+1$ 的最短路径的某一前缀。又当 $l=r$ 时，$S(l,r+1)$ 就是该路径本身；再有 $[p,q]\subseteq[l,r]\Longrightarrow S(l,r)\supseteq S(p,q)$，故本命题得证。

    因此，我们需将整条路径上的点的最大出现时间整体覆盖成 $t_{r+1}(x)=r$（$r+1$ 本身除外，它是 $t_{r+1}(r+1)=r+1$）。可以使用珂朵莉树和树剖维护连续的 $t(x)$ 相同的一段。设 $Φ$ 表示连续段个数。每次覆盖操作会对 $\newcommand\bigO{\operatorname{O}}\bigO(\log n)$ 条重链执行“删除若干连续段，加入 $\bigO(1)$ 个连续段”的操作。又 $Φ\leq n$，则 $Φ$ 的总变化量是 $\bigO(n\log n)$ 的。因此若用对数级别有序关联式容器（如 std::map），总时间复杂度为 $\bigO(n\log^2 n)$。
    （更多…）

  • 再探 FFT – DIT 与 DIF，另种推导和优化

    本文将简单推导两种方式进行的离散傅里叶变换，用另种视角解释并优化算法。参考了 Seniorious yhx-12243 的 NTT 到底写了些什么（详细揭秘） 一文、OI Wiki 快速傅里叶变换 条目 和 rushcheyo 转置原理及其应用 讲稿。

    离散傅里叶变换

    我们计算数列 $\{a_n\}$ 的离散傅里叶变换
    $$
    \newcommand\DFT{\operatorname{DFT}}\DFT(a,n)_k=\sum_{j=0}^{n-1}a_j\mathrm{e}^{\frac{-2\pi\mathrm{i}}{n}kj}
    $$

    由卷积定理和循环卷积得到，我们对同样长为 $n$ 的数列 $\{b_n\}$ 作 $\DFT$，并令数列 $c_k=\DFT(a,n)_k\DFT(b,n)_k$，则有
    $$
    \newcommand\IDFT{\operatorname{IDFT}}\IDFT(c,n)_k=\sum_{j+q\equiv k\pmod n}a_jb_q
    $$

    于是我们可以利用该原理实现常规意义下的数列卷积：有长为 $n$ 的数列 $\{a_n\}$，长 $m$ 的数列 $\{b_m\}$，则将 $a,b$ 高位补 $0$，分别作 $n+m-1$ 位的 $\DFT$，点值相乘后 $\IDFT$ 即可得到 $c_k=\sum_{i+j\equiv k\pmod{n+m-1}}a_ib_j=\sum_{\substack{i+j=k\\0\leq i<n\\0\leq j<m}}a_ib_j$。

    为行文方便，下文采用 $\DFT(a,n)_k=\sum_{i=0}^{n-1}a_i\omega_n^{ik}$ 的定义，其中 $\omega_n=\exp(2\pi\mathrm{i}/n)$，即 $n$ 阶单位根。 （更多…）

  • 高维莫队

    我们可以将莫队算法从一维扩展到更高维度。

    考虑正在维护 $k$ 维结构的信息，且每一维的大小分别为 $n_1,n_2,\cdots,n_k$。为了下文叙述方便，我们将维度大小序列复制一份，得到 $n_{k+1},\cdots,n_{2k}\quad(n_i=n_{i-k})$。我们同时维护 $2k$ 个指针，第 $i\ \ (i\leq k)$ 个指针维护第 $i$ 维左端点，第 $i\ \ (k<i\leq 2k)$ 个指针维护第 $i-k$ 维右端点。按询问处理顺序依次移动到每个询问对应的位置上。 （更多…）

  • MOCK ??? 20221012 日志

    $4$ 道题全部只会暴力。还不如直接发下来当练习做呢，省得在场上罚坐三小时浪费时间。

    简略题解

    A – 神灵庙

    观察发现：

    • 当树的形态确定时，我们总是将权值更大的节点安插到深度更小的叶子上。可以将 $a$ 降序排序后逐层填写。
    • 一个节点只可能有 $0$ 个或者 $2$ 个儿子。如果只有 $1$ 个儿子，显然可将该节点删除而整棵子树全部向上平移。

    设 $f(d,i,c_1,c_2)$ 表示“现在位于第 $d$ 层（此处“层”指的是节点实际深度）。已经填写好了 $a_1,a_2,\cdots,a_i$，且第 $d$ 层共 $c_1$ 个空置（非叶子）节点，第 $d-1$ 层有 $c_2$ 个此类节点”。那么两层的每一空置节点，均会有一个第 $d+1$ 层的儿子。枚举“下一层要填写 $k$ 个元素”，有转移
    $$f(d+1,i+k,c_1+c_2-k,c_1)\leftarrow f(d,i,c_1,c_2)+\left(\sum_{j=i+1}^{i+k}a_j\right)(d+1)$$ （更多…）

  • AtCoder ABC236G – Good Vertices – 题解 – 矩阵乘法优化DP

    昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。

    由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。

    今天查看题解，发现有几个重要的，从未考虑过的trick：

    1. 既然要求能够经恰好$L$次转移到达的最早的时间点，则我们将每条边的边权$w$设为其加入图中的时间，则可以转化成恰有$L$条边的最小瓶颈路。
    2. 发现$L$很大，所以考虑通过矩阵乘法加速递推，也即所谓倍增优化DP的一种。

    （更多…）