TH911 Blog

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

高维偏序

树套树三维偏序/高维偏序

不知道从哪里下的 PDF，感觉写的很好。 处理偏序问题时，如果偏序条件都带等号，则需要考虑两个元素完全相同的情况，这时需要该元素 $a$ 的统计个数 $\textit{cnt}$，然后统计满足偏序条件元素个数 $x$，则 $a$ 的答案为 $x-1$，同时直接做 $\textit{cnt}$ 的贡献。 一维偏序 排序即可。 二维偏序 排序之后树状数组统计即可。 比如逆序对...

Posted by TH911 on February 17, 2026

Link Cut Tree

LCT 动态树问题

Luogu P3690 动态树（LCT） 给定 $n$ 个点、每个点的权值和 $m$ 次操作： 0 x y 代表询问从 $x$ 到 $y$ 的路径上的点的权值的 $\operatorname{xor}$ 和。保证 $x$ 到 $y$ 是联通的。 1 x y 代表连接 $x$ 到 $y$，若 $x$ 到 $y$ 已经联通则无需连接。 2 x y 代表...

Posted by TH911 on February 16, 2026

题解：[POI 2001] 和平委员会

洛谷 P5782

题目传送门 题意分析 显然可以跑 2-SAT。 记 $f(x)$ 为 $x$ 的同一党派的代表。 那么，若 $i,j$ 彼此厌恶，建边 $i\rightarrow f(j),j\rightarrow f(i)$ 即可。 因为 $i$ 存在，则 $j$ 不存在，$f(j)$ 存在。$j\rightarrow f(i)$ 同理。 答案即在 $2i-1,2i$ 里选择拓扑序较大...

Posted by TH911 on February 15, 2026

2-SAT

例题：洛谷 P4782

SAT 给定 $n$ 个布尔变量 $x_1,x_2,\cdots,x_n$，和 $m$ 组关系，每组关系给定 $i_1,i_2,\cdots,i_k,a_1,a_2,\cdots,a_k$，表明： \[[x_{i_1}=a_1]\lor[x_{i_2}=a_2]\lor[x_{i_3}=a_3]\lor\cdots\lor[x_{i_k}]=1\] 求任意一组解。 SAT...

Posted by TH911 on February 14, 2026

题解：[JXOI2017] 加法

洛谷 P4064

题目传送门 题意分析 注意到「最小值尽可能的大」。 一般对于这种最值的最值的问题，都可以套一层二分答案。——xxy 考虑二分答案。 二分答案的原因 一直没想明白，直到我在模拟赛上打了 $\text{1.5h}$ 建了 $3$ 棵线段树维护的贪心假了后，终于想起来二分答案。 最值具有单调性，最值的...

Posted by TH911 on February 10, 2026

题解：[JOISC 2015] 有趣的家庭菜园 2 / Growing Vegetables is Fun 2

洛谷 P14407

题目传送门 题意分析 记原题面中 $n,H_i,P_i,C_i$ 分别为 $n,h_i,p_i,c_i$。 考虑 DP 求解最大收益，不难发现最终有效的 $h_i$ 一定是先上升在下降的。 对于这种「单峰」的东西，DP 可以考虑做两次：上升和下降，即从前往后 $h_i$ 不降和从前往后 $h_i$ 不增。 以 $h_i$ 不降为例，设 $\textit{dp}_{i,j}$...

Posted by TH911 on February 10, 2026

题解：To the moon

HDU4348

题目传送门 题意分析 显然是维护一棵可持久化线段树。 $1\leq n,m\leq 10^5$，很容易写完。但是发现空间限制 $\text{64MB}$，需要卡空间。 先丢掉线段树中存储的节点边界，放入递归中传参。 然后考虑继续卡，将可持久化线段树的懒标记改为标记永久化，这样可以避免每次 down 都要新建两个节点。（当然你写回收也可以，不过不好写。） AC 代码 1 ...

Posted by TH911 on February 10, 2026

树套树

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

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

要做一个优秀的 OIER

FRIENDS