Welcome to Liam's Blog

About me

My id : lnw143
Year of Birth : 2009
Location : Zhongshan, Guangdong Province, CHN

Motto

Nothing.

Links

2025年8月5日
分类于 Record
需要 3 分钟阅读时间

2025 年 8 月（及以前）做题记录

可能会不定时放一些远古时代的题目。

[NOI2005] 月下柠檬树

平面几何，自适应辛普森法求面积，预处理圆的公切线，求值时单点取 max。

复习一下 simpson 公式 $\dfrac {r-l} 6 (f(l)+f(r)+4f(\dfrac {l+r} 2))$。

注意如果超时可以去除层数的限制。

[HAOI2015] 数组游戏

博弈论翻棋子游戏 + 整除分块，感觉还是挺结论的。可能考场上打表或者认真思考也可以发现。

[PA 2022] Mędrcy

好像是随机跳到的？

考虑从 corner case 开始到一般，这种每个人都绝顶聪明的推理要从每个人的视角考虑是否出现矛盾，即假设自己没有不知道的咒语，看他人的反应和基本公理是否冲突，可推断自己的状态。

最后得出结论求最小点覆盖，由于点数 $k \le 30$，可用 $T(n) = T(n-1) + T(n-3)$ 的最小点覆盖做到可以接受的复杂度（朴素做法 $\mathrm{O}(2^k)$），参考。

有空补一下 CF164D。

【UR #6】懒癌

感觉还是比较抽象的，首先考虑一个人什么时候开枪，由于每个人都知道整个有向图，所以每个人可以从自己的狗没病的情况出发，在符合自己所见的情况中枚举所有可能状态，取最大值后+1即为开枪时间。转移成环的话都不开枪（相当于每个人都在等别人开枪）。

然后这个转化就抽象了，我们首先建一个有向图，图中边 $u \to v$ 存在当且仅当 $u$ 看不见 $v$，然后考虑一个病的状态 $s$，将有向图上的 $s$ 中的点染黑，发现每次选择一个人转移相当于枚举 $u \in s$，然后将 $u$ 染白，将 $u$ 的出边的一个子集染黑，求最大操作次数（做一次+1）。因为我们对有病的狗的主人的开枪时间取 min，所以每次只选除自己外可达前驱中没有黑点的黑点染白（不然的话选前驱会更小，前驱会再次染黑这个点，避免冗余操作）。显然黑点越多操作次数不降，而且转移成环相当于有向图中的一个环不停转圈，所以考虑缩点。如果一个强连通分量由至少 2 个点缩成，即存在环，那么这个强连通分量内以及它的前驱都不能染黑，否则没人开枪。然后考虑剩余点中染黑一个子集，发现策略是能染黑就染黑，且每个点只会染白一次，于是所有初始黑点的可达后继求个并集，大小就是开枪时间。

那么开枪人数呢？发现一个状态中开枪人数是取到 min 值的位置数，而为了取到 min 值，上面有提到只选除自己外前驱中没有黑点的黑点，计数是显然的。

用 bitset 优化求可达点集做到 $\mathrm{O}(\dfrac {n^3} \omega)$。

【UR #19】前进四

Segment Beats。

可以兔队线段树做到 2log，不足以通过。

考虑离线，对序列进行扫描线，维护时间轴。每次扫到一个数，它在时间轴上呈现若干个区间，且这些区间总个数是 $\mathrm{O}(n+q)$ 的。操作时对区间取 min 并记录有效取 min 次数，可以 Segment Beats $\mathrm{O}((n+q)\log n)$ 解决。

有空补线段树 3。

[NOI2018] 情报中心

赛时没有认真思考，感觉看完题解好像没什么难点。

关键在于想到将贡献分拆在 lca 上，然后是带权直径的板子，可能会有一点细节。正解是分讨，会复杂许多。

[NordicOI 2022] 能源网格 Power Grid

想着数论做法，一边 assert 一边拍验证结论，大脑直接放空，导致获得 0 分。

还是要独立思考，发现自己在无脑猜结论时出去洗把脸。

主要是思路错了，一直 dfs 导致极其低效，做了 1h 后就应该反思或者放弃，正解思路有一点重合，感觉还是没有 bfs 式想题。

[ROI 2024] 无人机比赛 (Day 2)

被低年级选手单调队列 /ll

重点在于发现前缀严格最大值只有 $\mathrm O(\sqrt n)$ 且只有这些位置有意义。然后拆贡献得到几个 $\sum$ 后再根号平衡下就可以得到 $\mathrm O(n \sqrt n)$ 的做法。

错误之一是没想到是根号，一直想 log 的部分分。然后是没拆贡献，感觉还是 trick 没有把握好。

[WC2016] 挑战NPC

一般图最大匹配，感觉还是挺考思维的。

AGC005E Sugigma: The Showdown

AGC 还是太吃思维了，什么时候可以战胜 /yiw

关键在于注意到如果一条边在另一树上两点距离大于 2 会 inf，于是只考虑距离为 1,2 的边。

又发现在对手的树上一定会深度递增（以对手起点为根），于是对手会不停向当前点走，即策略可定，dfs 找最优解即可。

P8864 「KDOI-03」序列变换

第一次被决策单调性打败，深刻认识到自己什么都不会。

赛时写了一个复杂 DP，没有想到更简单的形式，可能是后续优化没能进行的原因。

关键在于简单地刻画相邻两个不同位置最多 $k$ 个，发现可以刻画成最多 $\lfloor \dfrac k 2 \rfloor$ 连续的 1 段，奇数时特殊处理下。

于是用 $w_{l,r}$ 表示所有的 $[l,r]$ 中的 1 移动到一起的花费，因为一定取中位数为中心最优，可以 $\mathrm O(n^2)$ 预处理。

然后发现转移是 $k$ 次 $(\min,+)$ 矩阵乘法，于是快速幂做到 $\mathrm O(n^3 \log k)$，运用神秘的决策单调性可以做到 $\mathrm O(n^2 \log k)$。

[JOISC 2024 Day2] 棋盘游戏

可能看到 $5 \times 10 ^ 4$ 已经不知所措了，赛场上打了 17 分还挂了。

关键在于想到其他 $k-1$ 个棋子有两种决策，就是在两个棋子之间跳或者围着一个棋子跳，所以 $1$ 号点每多经过一个停止单元格就会增加至少 $k-1$ 的贡献，所以最多多经过 $\lfloor \dfrac n {k-1} \rfloor$ 个。于是有 $\mathrm O(\dfrac {n^2} k)$ 的做法。

然后发现 $k$ 很小的话可以枚举斜率去切凸包，跑 dij 可以做到 $\mathrm O(nk \log n)$。

平衡下可以做到 $\mathrm O(n \sqrt{n \log n})$。

细节有点多，考察了 01bfs 和 dij。主要难点在于想到一个点对答案贡献是斜率为 1 或 2 的函数，然后想到两种做法后平衡。

P13497 【MX-X14-T7】墓碑密码

FWT 计数题，主要是想到用 FWT 推式子，然后用 __int128 和 popcount 加速计算 $\sum_{j \in S} (-1)^{|i\cap j|}$，可能推式子需要一定的熟练度不然会推错或者做不出来，最后预处理组合数就好了。

还是有一定难度的，有空补利物浦集合。

[POI 2023/2024 R1] Satelity

$n + \lceil \log_2 n \rceil$ 是显然的，然后就懵逼了。

发现原来可以这么推：设左边 $s_l$，右边 $s_r$ 个等价类（不失一般性设 $s_l \le s_r$），设左边最大等价类有 $c_l$，右边有 $c_r$ 个，那么花费是 $s_l + \lceil \log_2 c_l \rceil + \lceil \log_2 c_r \rceil$，容易发现 $s_l \le n - c_l + 1$，$s_r \le n - c_r + 1$，又 $s_l \le s_r$，设 $x = \max (c_l,c_r)$，花费不会超过 $n-x+1+2\lceil \log_2 x \rceil$，这个东西超过 $n+1$ 是 $x=3$ 或 $x=5$ 的 corner case，特判即可。

还是比较思维的，以后束手无策时可以考虑设一些量推一推说不定发现上界。

P11692 [Ynoi Hard Round 2025] 《十字神名的预言者》宏伟（色彩）

lxl 安利的可持久化平衡树题。

先考虑 $r=n$ 的情况，发现相当于在值域上从某个区间复制而来，或者再重复几遍然后放到操作的定义域中，并且对其中一段异或上 $a$，于是可以用可持久化平衡树维护。

考虑一般情况下会出现什么状况，可能会产生 $r$ 以外的贡献导致答案出错。一般的想法是 pushdown 的时候记录下异或产生的位置并且不合并标记，但是空间可能爆炸。

这时候需要用到取模的性质，即一个数取模不超过 $\mathrm O(\log V)$ 次，因为一次取模至少减半。然后考虑 tag 用一个特殊节点表示，即操作点，只有一个儿子，节点本身有异或的信息。从节点内分裂出的子树要重新打上 tag，合并时不对特殊节点进行分裂。

考虑这样做树高时多少，发现从平衡树上一个普通节点往下走后如果不是走到特殊节点那么 size 减半，否则因为取模发生 $\log$ 次，所以特殊节点只经过 $\log$ 个，总树高还是 $\log$ 的。

这里用到了全局平衡思想，即把取模的 $\log$ 与平衡树的 $\log$ 相加而非相乘，得到更优的复杂度，类似于全局平衡二叉树从树剖处优化而来。

总时间复杂度 $\mathrm O(n \log n)$，不卡常。

2025年7月13日
分类于 Math
需要 2 分钟阅读时间

群论基础

定义

定义集合 $G$ 与在 $G$ 上的二元运算 $\times$，若其满足以下条件，则称 $(G,\times)$ 为一个群。

封闭性。$\forall a,b \in G,a \times b \in G$
结合性。$\forall a,b,c \in G,(a \times b) \times c = a \times (b \times c)$
单位元存在性。$\exists e \in G,\forall a \in G,e \times a = a \times e = a$
逆元存在性。$\forall a \in G,\exists b \in G,a \times b = b \times a = e$

性质

单位元唯一

$e_1 \times e_2 = e_1 = e_2$

逆元唯一

设 $a$ 有逆元 $b,c$，$c \times a \times b = e \times b = c \times e = b = c$

关于子群 & 陪集

对于群 $(G,\times)$，若 $H \subseteq G$，且 $(H,\times)$ 构成一个群，则称 $(H,\times)$ 为 $(G,\times)$ 的子群，简记为 $H \le G$。

对于 $H \le G,g \in G$，定义 $gH=\{g \times h \mid h \in H\}$，称为 $H$ 关于 $g$ 的左陪集。右陪集同理。

下面是陪集的若干性质。

$\forall g \in G, |gH| = |H|$
$\forall g \in G, g \in gH$ （这是因为 $e \in H$）
$gH = H \iff g \in H$
$aH = bH \iff b ^{-1} \times a \in H$
$aH \cap bH \not = \emptyset \Rightarrow aH = bH$
$H$ 所有的陪集并为 $G$。

Proof

(3) $g \in H \Rightarrow gH = H$，$g \not \in H, g \in gH \Rightarrow gH \not = H$

(4) $aH = bH \Rightarrow b^{-1} \times a H = H \Rightarrow b^{-1} \times a \in H$

(5) $aH \cap bH \not = \emptyset \Rightarrow \exists x,y \in H, ax = by \Rightarrow x \times y^{-1} = b\times a^{-1} \in H \Rightarrow aH = bH$

一些表述：

对于 $H \le G$，$G / H$ 表示 $G$ 中 $H$ 所有的左陪集 $\{gH \mid g \in G\}$。

对于 $H \le G$，$[G : H]$ 表示 $G$ 中 $H$ 不同陪集的数量。

关于记号

以下将群 $(G,\times)$ 简记为 $G$。

拉格朗日定理

对于有限群 $G$ 及其子群 $H$，有

\[ |H| \times [G:H] = |G| \]

即 $H$ 的阶乘 $G$ 中 $H$ 不同陪集的数量等于 $G$ 的阶。

理解：因为 $H$ 的所有陪集不交，大小都为 $|H|$，且并为 $G$，故不同的陪集有 $\frac { |G| } { |H| }$ 个。

群作用

对于群 $G$ 和集合 $X$，$G$ 中每个元素都是 $X$ 到自身的映射，记 $g \in G$ 将 $x \in X$ 映射为 $g(x)$，若所有映射满足以下条件，那么称群 $G$ 作用于集合 $X$ 上。

结合律。$\forall g_1,g_2 \in G,x \in X,g_1(g_2(x)) = (g_1 \times g_2)(x)$
单位元是恒等变换。$\forall x \in X,e(x) = x$

轨道-稳定子定理

对于群 $G$ 作用在集合 $X$ 上，称 $x \in X$ 的稳定子为 $G^x = \{g \mid g \in G, g(x) = x\}$，轨道为 $G(x) = \{g(x) \mid g \in G\}$。

定理内容：

\[ \forall x \in X, |G^x| \times |G(x)| = |G| \]

即任意 $X$ 中的元素，其轨道和稳定子的大小之积为群 $G$ 的阶。

考虑证明 $G^x$ 为 $G$ 的子群

首先有 $e \in G^x$

封闭性：对于 $\forall a,b \in G^x$，有 $a(x) = b(x) = x$，再根据 $a(b(x)) = (a \times b) (x)$，有 $a \times b \in G^x$。

结合性显然。

逆元：对于 $g \in G^x$，有 $g^{-1}(g(x))=(g^{-1} \times g)(x) = e(x) = x$，故 $g^{-1} \in G^x$。

故根据拉格朗日定理我们只需证明 $|G(x)|=[G:G^x]$。

2025年7月11日
分类于 Record
需要 1 分钟阅读时间

计数 DP 技巧

Cat Jumps

sort: 组合意义

将形如 $\prod _{i=1} ^{n} (x+i)$，其中 $x = \sum_i^n a_i$ 的式子转化为对每个点连一条出边 $j$，权值为 $c_i = a_j + [j \le i]$，所有方案中边权乘积之和。这是因为 $\sum \prod_i^n c_i = \prod_i^n \sum c_i$，而一个 $i$ 的所有方案中边权和恰为 $i+\sum a$，故相等。

之后用各类容斥技巧，以及第一、二类斯特林数进行计数。

2025年2月22日
分类于 Math
需要 3 分钟阅读时间

单位根相关

复数域下方程 $x^n = 1$ 恰好有 $n$ 个解，记 $\omega_n = e^{\frac {2 \text{i} \pi} n}$，则这 $n$ 个解恰好为 $1,\omega_n,\omega_n^2,\cdots,\omega_n^{n-1}$。我们将 $\omega_n$ 称作 $n$ 次单位根。

在运算中，有 $\omega_n = e^{\frac {2 \text{i} \pi} n} = \cos \frac {2 \pi} n + \text{i} \sin \frac{2 \pi} n$。

特别地，在模 $P$ 意义的数域下，有 $\omega_n \equiv g^{\frac {P-1} n} \pmod P$，其中 $g$ 是模 $P$ 意义下的原根。

基础公式

Lemma 1

\[ \sum _{i=0} ^{n-1} \omega_n^i = [n=1] \]

这是因为根据等比数列求和公式有原式 $= \frac{1 - \omega_n^n} {1 - \omega_n}$，当 $n>1$ 时该式分子为零分母不为零，当 $n=1$ 时原式等于 $1$。

Lemma 2

\[ [n|k] = \frac 1 n \sum _{i=0} ^{n-1} \omega _n ^{ik} \]

证明

当 $n|k$ 时，原式显然成立。
当 $n \nmid k$ 时，有 $\omega_n ^k \not = 1$，根据等比数列求和公式有 $$ \sum _{i=0} ^{n-1} \omega _n ^{ik} = \frac {1 - \omega_n ^{kn}} {1 - \omega_n ^k} = 0 $$

注意到 Lemma 1 是 Lemma 2 $k=1$ 时的特例。

Lemma 3

\[ [k \equiv a \pmod n] = \frac 1 n \sum_{i=0}^{n-1} \omega_n^{i(k-a)} \]

这是因为 $k \equiv a \pmod n \iff n \mid (k-a)$。

Lemma 2 和 Lemma 3 是 单位根反演 的重要公式。

单位根反演

设有多项式 $f(x)$，现在我们要求它在 $d$ 的倍数处的系数和，即 $\sum_{d \mid i} [x^i]f(x)$，但是难以求出这个多项式的系数序列，甚至是无限长的。这是我们就要用到单位根反演。

基本形式

$\sum_{d \mid i} [x^i]f(x) = \frac 1 d \sum_{i=0}^{d-1} f(\omega_d ^i)$。

证明考虑设 $f(x) = \sum _{i \ge 0} a_i x^i$，考虑对于一位 $a_j$，它贡献答案的系数为 $\sum _{i=0} ^{d-1} \omega_d ^{ij}$，根据 Lemma 2 这个式子等于 $d[d|j]$，因此原式易得。

由此以及 Lemma 3 我们容易得到更一般的形式：

\[ \sum _{i \equiv a \pmod n} [x^i] f(x) = \frac 1 n\sum _{i=0} ^{n-1} \omega_n ^{-ia} f(\omega_n ^i) \]

例题

LOJ 6485

给定 $n,s,a_{[0,4)}$，求

\[ \sum _{i=0} ^n \binom {n} {i} s^i a_{i \bmod 4} \]

solution

容易想到对于 $i \in [0,4)$ 分开统计贡献，我们由系数序列 $f_i = \binom n i s^i$ 得到函数 $f(x) = (1+xs)^n$，由单位根反演的基本形式容易在 $O(\log n)$ 内解决。

推荐例题：QOJ5370。

Luogu P5591

给定 $n,p,k$，询问

\[ \sum_{i=0}^n \binom n i \times p^{i} \times \left\lfloor \frac{i}{k} \right\rfloor \bmod 998244353 \]

保证 $k$ 是 $2$ 的 $[0,20]$ 次幂。

hint

$\left\lfloor \frac{i}{k} \right\rfloor = \frac {i - (i \bmod k)} k$

solution

将答案拆成 $\sum_i \binom n i p^i i$ 和 $\sum_i \binom n i p^i (i \bmod k)$ 两部分。

对于第一部分，我们有 $\binom n m = \frac n m \binom {n-1} {m-1}$，因此

\[ \begin{aligned} \sum_{i=0} ^n \binom n i p^i i & = n \sum_i \binom {n-1} {i-1} p ^i \\ & = n p (1 + p) ^{n-1} \\ \end{aligned} \]

最后一步由二项式定理易得。

第二部分使用单位根反演，对于 $i \in [0,k)$ 计算系数：

\[ \begin{aligned} \sum_{i=0} ^n \binom n i p^i (i \bmod k) & = \sum _{i=0} ^{k-1} i \sum_{j=0} ^n [i \equiv j \pmod k] \binom n j p^j \\ & = \sum _{i=0} ^{k-1} i \sum_{j=0} ^n \sum_{t=0} ^{k-1} \omega_k^{t(j-i)} \binom n j p^j \\ & = \sum _{i=0} ^{k-1} i \sum_{t=0} ^{k-1} \omega_k^{-it}\sum_{j=0} ^n \omega_k^{tj} \binom n j p^j \\ & = \sum _{i=0} ^{k-1} i \sum_{t=0} ^{k-1} \omega_k^{-it}\sum_{j=0} ^n \binom n j (\omega_k^tp)^j \\ & = \sum _{i=0} ^{k-1} i \sum_{t=0} ^{k-1} \omega_k^{-it} (1 + \omega_k^t p)^n \\ & = \sum _{i=0} ^{k-1} i \sum_{t=0} ^{k-1} \omega_k^{-it} g(t) & \bigg(g(x) = (1 + \omega_k^x p)^n \bigg) \\ & = \sum _{i=0} ^{k-1} i f(\omega_k^{-i}) & \bigg(f(x) = \sum_{i=0} ^{k-1} g(i)x^i\bigg) \\ \end{aligned} \]

算式中的 $g(x)$ 我们可以在 $O(k \log n)$ 的时间内求出，而对于求 $f$ 在单位根处的点值，我们可以通过 NTT 在 $O(k \log k)$ 时间内求出，总时间复杂度 $O(k(\log k + \log n))$。

当然本题还有更简单的做法，即在公式倒数第二步交换 $i,t$ 的求和顺序，然后就是求一个 $S(n,x) = \sum_{i=0} ^n i x^i$，可以用类似等比数列求和的技巧做到 $O(\log n)$ 时间内求解。

Luogu P10664

给定整数 $n,k,p$，要求计算下列式子对 $p$ 取模的值：

\[\sum_{i=0}^n [k|i] \binom n {i} F_{i}\]

其中：

$p$ 为质数，且 $p$ 除以 $k$ 的余数为 $1$。
$F_n$ 为斐波那契数列，即 $F_0=1$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$。

hint

Fibonacci 数列看起来很棘手，难以将其转化为多项式函数。

但是别忘了它可以用矩阵快速幂计算，我们可以将函数变为从矩阵到矩阵的映射，从而将 $F_i$ 变成 $x^i$。

solution

先忽略 $k$ 的限制，我们要求 $\sum_i \binom n i F_i$。

我们设 Fibonacci 转移矩阵为 $X$，则原式为 $(I + X)^n$。

最后设 $f(x)=(I+Xx)^n$ 即可使用单位根反演快速计算。

注意 $n$ 要开到 long long 范围。

参考

2025年2月14日
分类于 Theory
需要 1 分钟阅读时间

定理

这里是一些常见的定理。

Hall 定理

2025年2月14日
分类于 Theory
需要 1 分钟阅读时间

Hall 定理

定理内容

对于二分图 $G=(V,E)$，设其左、右部点集大小分别为 $n,m(n \le m)$。

对于左部点集的任意子集 $S$，定义其邻域 $N(S)$ 为点集内点与右部点相连的点集，即 $N(S) = \{v|\exists u \in S, (u,v) \in E\}$。

则该图有完美匹配的充要条件为 $\forall S,|S| \le |N(S)|$。

证明

必要性显然，充分性可递归证明。

设当前左部点为 $S$，对于 $u \in S$，考虑为其寻找一个匹配点。

若 $N(S\setminus \{u\}) = N(S)$，任选 $v \in N(S)$ 作为 $u$ 的匹配点即可。

否则选择在 $N(S)$ 中但不在 $N(S\setminus \{u\})$ 中的点，这些点接下来也没法被匹配，所以不影响下面的过程。

于是我们将问题集合减小了 1，条件不变，递归构造即可。

扩展

二分图 $G=(V,E)$ 的最大匹配为 $|V| - \max_{S \subseteq V} \{ |S| - |N(S)| \}$。

证明参考 https://www.zhihu.com/question/622760742

例题

参考

https://www.cnblogs.com/yspm/p/15184873.html

2024年8月7日
分类于 String
需要 1 分钟阅读时间

字符串

这里是一些字符串相关的算法。

后缀数组

2024年8月7日
分类于 String
需要 4 分钟阅读时间

后缀数组

后缀数组是处理字符串的利器。

定义

对于长度为 $n$ 的字符串 $s = s_1 s_2 \cdots s_n$，定义 $s[i,j] = s_i s_{i+1} \cdots s_j$，即 $s$ 的第 $i$ 个到第 $j$ 个字符形成的子串。

定义 sa 为 $s$ 的后缀数组，sa[i] 表示第 $i$ 小的后缀的编号。

定义 rk[sa[i]]=i，即 rk[i] 表示后缀 $i$ 的 rank。

求解

考虑最暴力的做法，取出所有后缀并排序，空间复杂度 $O(n ^ 2)$，时间复杂度 $O(n^2 \log n)$。

考虑倍增，设 rk[j][i] 表示在所有长度为 $2^j$ 的后缀中，后缀 $s[i,i+2^j-1]$ 的 rank（超出 $n$ 的部分记为空字符，小于任何非空字符）。

显然我们可以 naively 得到 rk[0][i]，考虑如何由 rk[j-1] 得到 rk[j]。

发现可以将所有二元组 (rk[j-1][i],rk[j-1][i+(1<<(j-1))] 排序，即把每段后缀分为前后两段，并以前一半的 rank 作为第一关键字，后一半的 rank 作为第二关键字，超出 $n$ 的部分记为 0，排序后得到 rk[j]。

总共倍增 $\mathrm O(\log n)$ 次，每次排序 $\mathrm O(n \log n)$，总时间复杂度 $\mathrm O(n \log^2 n)$。

发现 rk 的值域是 $\mathrm O(n)$ 的，因此可以用桶排做到 $O(n \log n)$。

在算法竞赛中这已经足够了，如果追求更优的时间复杂度，可以考虑 SA-IS / DC3 算法，线性时间复杂度，但实现十分复杂，在竞赛中不常用，因此不再赘述。

显然通过 rk 可以 $\mathrm O(n)$ 得到 sa。

height 数组

定义 ht[i] 为后缀 sa[i] 与 sa[i-1] 的最长公共前缀的长度，并设 ht[1]=0。

一眼看来似乎没有线性做法，但是我们将尝试证明以下引理：

Lemma: ht[rk[i]] $\ge$ ht[rk[i-1]]-1。

Proof:

ht[rk[i-1]] $\le 1$ 的情况是 naive 的。

若 ht[rk[i-1]] $\ge 2$，即 sa[rk[i-1]-1] 与 i-1 的最长公共前缀长度 $\ge 2$，设这个最长公共前缀为 $aA$，其中 $a$ 是单个字符，$A$ 是一个非空字符串。

那么设后缀 sa[rk[i-1]-1] 为 $aAB$，i-1 为 $aAC$，则 $B \lt C$，且后缀 sa[rk[i-1]-1]+1 为 $AB$，i 为 $AC$。

后缀 sa[rk[i]-1] 因为只比 i 前一名，所以是小于 i 中最大的，又因为 $AB \lt AC$，所以 $AB \le$ 后缀 sa[rk[i]-1] $\lt AC$，容易看出后缀 i 和后缀 sa[rk[i]-1] 有公共前缀 $A$。

于是 ht[rk[i]] $\ge |A| = $ ht[rk[i-1]]-1。

$\square$

由此，我们从 ht[rk[i-1]]-1 开始暴力拓展 ht[rk[i]]，在 $\mathrm O(n)$ 的时间复杂度内得到 ht。

ht 数组有这样一个性质：后缀 i,j 的最长公共前缀长度等于 ht[rk[i],rk[j]) 中的最小值。（钦定 rk[i] $\lt$ rk[j]）

因此我们可以用 ST 表 $\mathrm O(n \log n)$ 预处理后 $\mathrm O(1)$ 询问任意后缀的最长公共前缀长度。

例题

UOJ 35.后缀排序

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5;
int n,sa[N + 2],cnt[N + 2],rk[2][N + 2],ht[N + 2];
char s[N + 2];
struct node {
    int x,y,id;
} p[N + 2],q[N + 2];
bool operator<(const node& a,const node& b) {
    return a.x!=b.x?a.x<b.x:a.y<b.y;
}
bool operator==(const node& a,const node& b) {
    return a.x==b.x&&a.y==b.y;
}
void Sort() {
    memset(cnt,0,sizeof(*cnt)*(n+1));
    for(int i=1; i<=n; ++i) ++cnt[p[i].y];
    for(int i=1; i<=n; ++i) cnt[i]+=cnt[i-1];
    for(int i=n; i>=1; --i) q[cnt[p[i].y]--]=p[i];
    memset(cnt,0,sizeof(*cnt)*(n+1));
    for(int i=1; i<=n; ++i) ++cnt[q[i].x];
    for(int i=1; i<=n; ++i) cnt[i]+=cnt[i-1];
    for(int i=n; i>=1; --i) p[cnt[q[i].x]--]=q[i];
}
int main() {
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1; i<=n; ++i) cnt[s[i]]=1;
    for(int i=1; i<128; ++i) cnt[i]+=cnt[i-1];
    for(int i=1; i<=n; ++i) rk[0][i]=cnt[s[i]];
    for(int j=1,k=1; j<=n; j<<=1,k^=1) {
        for(int i=1; i<=n; ++i) p[i]={rk[k^1][i],i+j<=n?rk[k^1][i+j]:0,i};
        Sort();
        for(int i=1,t=0; i<=n; ++i)
            if(i>1&&p[i]==p[i-1])
                rk[k][p[i].id]=t;
            else
                rk[k][p[i].id]=++t;
        if((j<<1)>n) swap(rk[k],rk[0]);
    }
    for(int i=1; i<=n; ++i) sa[rk[0][i]]=i;
    for(int i=1; i<=n; ++i) printf("%d ",sa[i]);
    putchar('\n');
    for(int i=1; i<=n; ++i) {
        if(rk[0][i]==1) continue;
        int k=i>1?max(0,ht[rk[0][i-1]]-1):0;
        while(i+k<=n&&sa[rk[0][i]-1]+k<=n&&s[i+k]==s[sa[rk[0][i]-1]+k]) ++k;
        ht[rk[0][i]]=k;
    }
    for(int i=2; i<=n; ++i) printf("%d ",ht[i]);
    return 0;
}

2024年8月6日
分类于 Misc
需要 1 分钟阅读时间

杂项

这里是一些杂七杂八的东西。

VSCode 配置

2024年8月6日
分类于 Misc
需要 2 分钟阅读时间

VSCode 配置

前言

作为 VSCode 资深用户，从第一次下载到如今，踩了一个又一个坑，在这里记录一下我的配置方法以及遇到的一些问题。

准备

在官网下载后，点开安装程序，建议勾选以下所有选项：

VSCode 安装程序

等待安装完毕即可。

插件

插件是 VSCode 的核心，其强大的插件开发社区是一大亮点。

打开左侧的扩展管理器，搜索并点击安装便可将插件添加到 VSCode。

如搜索 chinese，安装中文语言包。

可以在终端用 code --install-extension <extension-id> 或按 F1 / Ctrl+Shift+P 打开命令面板，搜索 ext install 并选择 Extensions: Install Extension，输入插件名称或 ID 安装插件。

附录有一些常用的插件。

配置

VSCode 默认是不支持编译运行 C++ 的，需要安装插件 C/C++ 并配置文件。

Ctrl+K Ctrl+O 打开一个工作文件夹，并新建 .vscode 文件夹，并新建两个文件 tasks.json 和 launch.json。

Tasks

tasks.json 文件用来配置编译任务，可以配置多个编译任务，每个任务对应一个编译命令。

尝试在 tasks.json 文件中添加以下内容：

{
    "tasks": [
        {
            "type": "cppbuild",
            "label": "C++14",
            "command": "g++",
            "args": [
                "${file}",
                "-o",
                "${fileDirname}\\a.exe",
                "-std=c++14",
                "-Wall",
                "-Wextra",
                "-g",
                "-Wl,--stack=128000000",
                "-fno-ms-extensions"
            ],
            "options": {
                "cwd": "${fileDirname}"
            },
            "problemMatcher": [
                "$gcc"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            }
        },
        {
            "type": "cppbuild",
            "label": "C++14 With O2",
            "command": "g++",
            "args": [
                "${file}",
                "-o",
                "${fileDirname}\\a.exe",
                "-std=c++14",
                "-O2",
                "-Wall",
                "-Wextra",
                "-g",
                "-Wl,--stack=128000000",
                "-fno-ms-extensions"
            ],
            "options": {
                "cwd": "${fileDirname}"
            },
            "problemMatcher": [
                "$gcc"
            ],
            "group": {
                "kind": "build",
                "isDefault": false
            }
        },
    ],
    "version": "2.0.0"
}

其中 label 字段是任务的名称，command 字段是编译器，args 字段是编译命令，cwd 字段是编译命令的运行目录，isDefault 字段是是否为默认编译任务。

之所以输出为 a.exe，是为了兼容源代码文件名中的中文字符，如果不需要，可以改为 ${fileBasenameNoExtension}.exe。

Warning

非必要不要更改 cwd，type，problemMatcher等字段，否则可能导致任务执行失败。

Launch

launch.json 文件用来配置调试任务，可以配置多个调试任务，每个任务对应一个调试命令。

尝试在 launch.json 文件中添加以下内容：

{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "Launch Program",
            "type": "cppdbg",
            "request": "launch",
            "program": "${fileDirname}\\a.exe",
            "args": [],
            "stopAtEntry": false,
            "cwd": "${fileDirname}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "gdb",
            "setupCommands": [
                {
                    "description": "Enable pretty-printing for gdb",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                }
            ],
            "preLaunchTask": "C++14"
        }
    ]
}

其中一般只需要配置 preLaunchTask 与 program 字段，前者指定编译任务，后者指定运行程序。

全局配置

你是否有这样的烦恼：每次新建 VSCode 工作文件夹都要配置 tasks.json 和 launch.json？每次编译都会自动生成 .vscode 文件夹？

VSCode 的全局 tasks.json 配置位于 %APPDATA%\Code\User\tasks.json，可以编辑该文件来配置全局编译任务。

而 launch.json 配置位于 %APPDATA%\Code\User\settings.json，在其中加入以下内容：

"launch": < launch.json 配置内容 >

这样即可实现一次配置，终身受益（