TH911 Blog

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

树套树

洛谷 P3332

题目传送门 维护 $n$ 个可重集，初始都是空集，有 $m$ 个操作： 1 l r c：表示将 $c$ 加入到编号在 $[l,r]$ 内的集合中 2 l r c：表示查询编号在 $[l,r]$ 内的集合的并集中，第 $c$ 大的数是多少。 树套树 对于多维度信息，我们可以使用树套树维护。 顾名思义，即建一棵树，而这个树上的每一个节点都包含一...

Posted by TH911 on February 9, 2026

题解：[ONTAK2015] Stumilowy sad

洛谷 P8024

题目传送门 如果你不会 Segment Tree Beats/吉司机线段树。 题意分析 区间操作，想到线段树是显然的，对于四个操作： 给 $[l,r]$ 增加 $x$。 给 $[l,r]$ 对 $x$ 取 $\min$，记为 $\operatorname{chkmin}$。 这个有一点意思。 一开始以为是区...

Posted by TH911 on February 9, 2026

可持久化 Trie

例题：洛谷 P4735

可持久化 Trie Trie 树的可持久化思路与线段树/平衡树类似，每次都 clone 一个新的节点即可。 唯一需要注意的是实现上的问题，因为 Trie 树一般不写递归，因此要注意实现。 一般实现的可持久化 Trie 都是 01Trie。 Luogu P4735 最大异或和 给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ 和 $m$ 次操作： ...

Posted by TH911 on February 9, 2026

题解：[湖南集训] 更为厉害

洛谷 P3899

题意分析 $q$ 次询问，每次询问给出树上节点 $a$ 和 常数 $k$，求满足 $a,b$ 均为 $c$ 的祖先且 $\operatorname{dist}(a,b)\leq k$ 的方案数。 可以发现，$c$ 一定在 $a$ 的子树内；那么 $b$ 相对于 $a$ 的位置关系为： $b$ 是 $a$ 的祖先。 而 $c$ 可以在子树 $a$ 内随便取（除了...

Posted by TH911 on February 8, 2026

树分治

点分治 基本原理 点分治，即将树以节点为分界点划分为若干个部分，从而将一个大规模问题转化为了若干个相同的小规模问题，从而解答。 点分治常常用于处理树上路径信息。 考虑一棵树，根节点为 $x$，子节点分别为 $v_1,v_2,\cdots,v_s$。 那么这棵树内，路径可以被分为两种： 经过 $x$，从子树 $v_i$ 出发，到达子树 $v_j$ 内部的。（也可以一端在在 $...

Posted by TH911 on February 8, 2026

线段树区间最值/区间历史最值

吉司机线段树 Segment Tree Beats

Still writing… 2016 年国家集训队论文 Segment Tree Beats!：$2016$ WC 交流课件。 Segment Tree Beats，吉司机线段树，由吉如一在 $2016$ 年国家集训队论文中提出。 在本文中，$\leftarrow$ 表示赋值。 下文中，可能会出现区间最值操作 $\mathcal O(m\log n)$ 的...

Posted by TH911 on February 5, 2026

题解：[AHOI2017/HNOI2017] 影魔

洛谷P3722

题目传送门 题意分析 $p_1,p_2$ 无关，分开计算贡献是显然的。 考虑如何刻画贡献。 记询问区间为 $[l,r]$，原序列为 $a_1,a_2,\cdots,a_n$。 那么： $(i,j)$ 产生 $p_1$ 贡献当且仅当（和 $j=i+1$ 时恒有 $p_1$ 贡献）： \[\max_{k=i+1}^{j-1}a_k<\min(a_i,a...

Posted by TH911 on February 5, 2026

题解：楼房重建

洛谷P4198

题目传送门 题意分析 设第 $i$ 栋楼房的高度为 $h_i$。 那么 $(i,h_i)$ 能被看见当且仅当： \[\max_{j=1}^{i-1}\dfrac{h_j}j<\dfrac{h_i}{i}\] 记 $k_i=\dfrac{h_i}i$，则题意即动态维护一个序列，$k_1$ 必须选，且选中的 $k_i$ 均为前缀严格最大值。 普通静态方法都不行，不能接受...

Posted by TH911 on February 5, 2026

线段树区间最值/区间历史最值

吉司机线段树 Segment Tree Beats

Still writing… 2016 年国家集训队论文 Segment Tree Beats!：$2016$ WC 交流课件。 Segment Tree Beats，吉司机线段树，由吉如一在 $2016$ 年国家集训队论文中提出。 在本文中，$\leftarrow$ 表示赋值。 下文中，可能会出现区间最值操作 $\mathcal O(m\log n)$ 的...

Posted by TH911 on February 4, 2026

题解：[BJOI2018] 链上二次求和

洛谷P4458

题目传送门 题意分析 原来线段树可以维护单点加多项式。 原链即序列，设为 $a_1,a_2,a_3,\cdots,a_n$。 记 $\displaystyle s_n=\sum_{i=1}^na_i,t_n=\sum_{i=1}^ns_i$。 那么容易发现，答案为： \(\begin{aligned} \sum_{d=l}^r\sum_{i=1}^{n-d+1}\s...

Posted by TH911 on February 3, 2026

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

要做一个优秀的 OIER

FRIENDS