TH911 Blog

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

题解：[春季测试 2023] 圣诞树

洛谷P9119

题目传送门 题意分析 首先确定起点 $k$ 是简单的。记 $a_1,a_2,\cdots,a_n$ 为原来的 $n$ 个点。 可以统一将 $a_1,a_2,\cdots,a_k$ 与 $a_{k+1},a_{k+2},\cdots,a_n$ 交换在序列中的位置，这样便于处理。交换后仍然为凸多边形。 考虑原问题等价于对新的 $a_1,a_2,\cdots,a_{n-1}$ 进行...

Posted by TH911 on August 16, 2025

各类模板

矩阵乘法 Barrett 约减

矩阵乘法 Matrix，支持二维 initializer_list 初始化。支持矩阵加法、矩阵乘法。重载 +、+=、*、*=。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47...

Posted by TH911 on August 15, 2025

Barrett 约减

优化整数除法/取模

推荐一篇文章。 Barrett 约减优化整数除法/取模 取变量的模其实是非常慢的，而 Barrett 可以在一定情况下将取模化为两次乘法、一次右移以及至多两次减法。 令模数为 $p$。 容易发现： \[x\bmod p=x-p\left\lfloor\dfrac xp\right\rfloor\] 考虑快速求出 $\left\lfloor\dfrac xp\right\r...

Posted by TH911 on August 15, 2025

线段树历史操作

历史和线段树

历史和线段树 例题：Loj P193 线段树历史和 您需要写一种数据结构，来维护一个有序数列，其中需要提供以下操作： 区间加一个数。 查询区间的历史和。 历史和定义为数列 $h_i$ 的区间和：初始 $h_i=a_i$，在每次操作（修改或查询）完成后，对所有 $h_i \leftarrow h_i+a_i$。 考虑使用线段树维护区间信息。...

Posted by TH911 on August 15, 2025

题解：Koishi Loves Number Theory

洛谷P3598

题目传送门 数学推导 首先不难得到： \[\begin{aligned} f(n)&=\sum_{i=0}^nx^i\\ &=\dfrac{x^{n+1}-1}{x-1} \end{aligned}\] 因为 $\operatorname{lcm}\left(\dfrac ac,\dfrac bc\right)=\dfrac{\operatorname{lcm...

Posted by TH911 on August 14, 2025

题解：最小公倍佩尔数

洛谷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

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

要做一个优秀的 OIER

FRIENDS