TH911 Blog

「光阴不可测，岁月亦无歌。」

题解：最小公倍佩尔数

洛谷P10663

题目传送门 gcd-lcm 容斥 所谓 gcd-lcm 容斥，即对于集合 $T$，有： \[\operatorname*{lcm}_{i\in T}i=\prod_{S\subseteq T}\left(\gcd_{i\in S}i\right)^{(-1)^{\vert S\vert-1}}\] 证明 不妨考虑 $i$ 的质因子。发现对于...

Posted by TH911 on August 14, 2025

树链剖分详解（长链剖分）

长链剖分应用 | 例题：洛谷P5903 CF1009F

参考资料 例题：P5903 树上 $k$ 级祖先。 例题：CF1009F Dominant Indices。 因为当时写树链剖分详解（重链剖分）时并不会长链剖分，所以只能另开一文了。 「长链剖分」，除「重链剖分」外的另一种树剖方式，与深度相关。 长链剖分 定义「重子节点」表示子树深度最大的子节点，「轻子节点」表示剩余子节点。其余定义同「重链剖分」的...

Posted by TH911 on August 13, 2025

可持久化并查集

例题：洛谷P3402

例题链接 建议优先阅读可持久化线段树。 可持久化并查集 可持久化并查集，即可撤销并查集，支持回退到之前某个版本信息。 显然需要维护 $f_x$ 为 $x$ 的父节点。使用可持久化线段树维护 $f_x$ 即可。 但是，注意可持久化并查集不能使用路径压缩，只能使用启发式合并优化。否则会破坏历史版本信息。 单次寻找根节点的复杂度为 $\mathcal O(\log n)$。...

Posted by TH911 on August 13, 2025

函数指针用法

有些时候需要函数指针，例如线段树建树时的初始值。 使用方法： 1 2 3 typedef int (*fp)(int); //... fp func 这样，func(x) 即一个返回 int 的函数。

Posted by TH911 on August 13, 2025

可持久化 FHQ Treap

例题：洛谷P3835

例题链接 建议优先阅读可持久化线段树。 可持久化 FHQ Treap 同可持久化线段树，可持久化平衡树的原理也是充分利用过去版本信息。 在 split 操作中，不断复制节点即可构造新版本。 是的，结束了。 事实上，诸多可持久化数据结构都是如此原理。 例题 AC 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2...

Posted by TH911 on August 13, 2025

题解：[CSP-S 2024] 染色

P11233

题目传送门 题意分析

Posted by TH911 on August 12, 2025

线段树优化建图

例题：CF786B

例题链接 给定一张 $n$ 个点的图，完成 $q$ 次建边操作，每次建边有权值： 建有向边 $v\rightarrow u$。 对于 $i\in[l,r]$，建边 $v\rightarrow i$。 对于 $i\in[l,r]$，建边 $i\rightarrow v$。 求最终图的最短路。 满足 $1\leq n\leq10^5$...

Posted by TH911 on August 12, 2025

题解：[JOISC 2022] 监狱

洛谷P9520

题目传送门 朴素图论建模 记 $s_x,t_x$ 分别表示囚犯 $x$ 的起点、终点，$\set{s_x\rightarrow t_x}$ 表示囚犯 $x$ 走过的点集。 对于囚犯 $u,v$： 若 $s_u\in\set{s_v\rightarrow t_v}$，则 $u$ 比 $v$ 先走，否则会被挡住。 若 $t_u\in\set{s_v\rightarrow...

Posted by TH911 on August 12, 2025

题解：[GDCPC 2024] 图

洛谷P13356

题目传送门 充分发扬人类智慧。 题意分析 首先考虑到 $k=\left\lceil\dfrac m{n-1}\right\rceil$，这应当有一些性质，因为 $k$ 并不是一个输入的给定值。 考虑到 $n-1$ 应当有什么用，注意到 $n-1$ 条边会构成一棵 $n$ 个节点的树。 因此启发我们可以考虑将边分组，维护 $k$ 组。理想情况是前 $k-1$ 组均有 $n...

Posted by TH911 on August 12, 2025

题解：[Vani有约会] 雨天的尾巴 /【模板】线段树合并

洛谷P4556

题目传送门 树链剖分做法 显然可以树链剖分维护链上信息，操作离线，按 $z$ 从小到大操作即可。 时间复杂度 $\mathcal O\left(m\log^2n\right)$。 线段树合并做法 对于每一个点都开一个动态开点权值线段树记录收到的救济粮数量。 操作路径可以进行树上差分转化为 $4$ 次操作。 即修改 $x\sim y$ 的路径时，修改四个点： $x...

Posted by TH911 on August 11, 2025

FEATURED TAGS
树状数组 题解 省选/NOI− 提高+/省选− DP 基础算法 普及+/提高 数学 线段树 贪心 普及/提高− 组合数学 字符串 未完 二分 图论 平衡树 数论 树形 DP Tarjan 位运算 搜索 Trie 二分答案 状态压缩 无聊时候的一点思考 最短路 FHQ Treap NOI/NOI+/CTSC 前端 前缀和 树链剖分
ABOUT ME

要做一个优秀的 OIER

FRIENDS