DS1
P5327 [ZJOI2019] 语言
拆点对，对每个点求出包含该点的路径并的大小作为该点的贡献，答案为所有点的贡献之和除以 \(2\)。
路径并不好处理，发现可以把包含该点的每条链的两个端点取出来，它们的极小生成树即为路径并。
经典结论：若干个关键点 \(a_1, a_2, \dots, a_m\)（\(a\) 按照 dfs 序从小到大排序）的极小生成树 \(T\) 的大小可以如下计算：
简单说明一下：考虑构建虚树的过程，先假设把 \(1\) 号点加进关键点集合，对 \(|T|\) 贡献大小 \(d_1\)，之后每一次加点，都贡献第 \(i\) 个点到它与上一个点的最近公共祖先的距离，由于一开始加入了 \(1\) 号点，因此需要把它对 \(|T|\) 的影响撤销掉，即 \(1\) 号点到所有点的最近公共祖先的距离。而求多个点的最近公共祖先又用到了一个结论：它们的最近公共祖先就是 dfs 序最小节点与 dfs 序最大节点的最近公共祖先。
如何维护这个关键点的集合？
可以想到用树上差分的形式，对于一条路径 \((u, v)\)，在 \(u, v\) 处打上添加标记，在 \(lca\) 及其父节点处打上删除标记。
开 \(n\) 个桶做这件事情，时间复杂度为 \(O(n^2\log{n})\)。
观察这是一个子节点向父节点 合并信息 的事情，可以用线段树合并维护，做到 \(O(n\log^{2}{n})\)。
如果采用欧拉序 + ST表求 LCA，以上出现的时间复杂度均可砍掉一只 \(\log\)。注意不要把 dfs 序和欧拉序搞混了。
P2305 [NOI2014] 购票
记 \(f_{i}\) 表示 \(i\) 节点处的答案。\(f_1 = 0\)。记 \(d_i\) 表示根节点到点 \(i\) 的距离，容易得到 \(O(n^2)\) 的 dp 转移：
设 \(y = f_i - d_i \times p_i - q_i, slope = -d_j, x = p_i, b = f_j\)，这是一个斜率优化的形式。
但我们更应该注意，\(y = slope\times x + b\) 的一次函数形式可以用李超线段树维护，并且容易在树上实现撤销。
麻烦在于有 \(d_i - d_j \le l_i\) 的限制，那么需要实现任意一条链上的线段并的信息查询。
首先考虑序列上的区间查询，可以采用 线段树套李超线段树，外层线段树的叶节点存每个位置的一条线段，外层线段树上的一个节点将其子树内包含的所有线段并起来。这个过程并不用真的进行 pushup，而是对每一条线段直接插到外层线段树上的 \(\log\) 个节点（的李超线段树）上去。
然后考虑树上的区间查询。一种 naive 的想法是树链剖分，做到时间复杂度 \(O(n\log^3{n})\)，空间复杂度 \(O(n\log{n})\)（考虑线段总数为 \(O(n)\)，每条线段至多插入 \(O(\log{n})\) 次，由于李超线段树的特性——信息并不一定要保存在叶节点，因此遇到空节点就会立即 return，也就是说，插入一条线段最多导致动态开出 \(1\) 个点，所以外层线段树上所有节点的李超线段树的节点总数是 \(O(n\log{n})\) 的）。
优化：将外层线段树上的叶节点对应的下标定义为原树上节点的 出栈序（最后一次被遍历到的时间顺序）。在 dfs 的过程中，记 \(ord_i\) 表示点 \(i\) 的出栈序，若能更新一个点 \(u\) 的最远点为 \(v\)，则外层线段树上区间查询 \(ord_u\) 到 \(ord_v\) 即可得到 \(u \to v\) 的链上所有线段并的结果。可以这样做的正确性保证在于，\(ord_u \sim ord_v\) 中对应两类点，一类是 \(u \to v\) 链上的点，另一类是不在链上的点，而后者此时一定未被遍历，信息未被上传，因此在 \(ord_u \sim ord_v\) 内的查询是十分精确的。
该做法的时间复杂度为 \(O(n\log^2{n})\)，空间复杂度仍为 \(O(n\log{n})\)。
总结一下此题给我印象极深的两点：
-
“线段并” 这个一眼李超线段树合并的东西，通过外层套上一棵线段树，将多条线段的 “合并” 转化为每条线段的 “插入”。
在外层线段树上维护线段并，本质上与李超线段树合并擅长维护的 “子树信息合并到父节点” 的问题（如 CF932F Escape Through Leaf）本质相同。但在这里，初始时所有线段都处于叶节点处。在我们构建出的深度为 \(O(\log{n})\) 的外层线段树中，暴力将一条线段插入到包含它的所有节点中，时间复杂度是正确的（\(O(n\log^2{n})\)），因此没有必要进行李超线段树合并；而对于普通的李超线段树合并问题，每个节点都会挂一条线段，并且树的深度无法保证，所以就不能暴力考虑分别插入每条线段，否则时间复杂度会退化成 \(O(n^2\log{n})\)，甚至不如暴力。
-
树上链查询的问题可以考虑 出栈序。看似多考虑了节点信息，实则并没有真正查询到这些信息。
一对时间戳在岔路间流动着。我的时间戳站在谷底接受漫天星火的审判。审判之下，岁月的鸿沟被过往湮灭于黑暗，那里是我将要驻足的地方。
P3688 [ZJOI2017] 树状数组
九条可怜把树状数组写反了，这个错误的玩意相当于在求异或后缀和。
询问 \((l, r)\) 正确的概率，相当于询问 \(A_{l - 1} = A_r\) 的概率；修改操作相当于等概率地将 \((l, r)\) 内的一个点进行取反。
一个位置上的值显然只与其被修改的次数有关，相当于询问 \(A_{l - 1}\) 与 \(A_r\) 被修改次数的奇偶性相等的概率。
P4729 [HNOI2009] 积木游戏
2023.09.06。八个月前做这个题调了六个小时。现在看来，除开欧拉定理的部分，整道题的思路极其清晰易懂，虽然码量大，但并不难码。尽管如此，融合了数据结构、图论（模型构建 + 三元环计数）、拓扑论（欧拉定理）多方面知识点，而且还有四面共角的细节问题，它仍然算得上是一道高位紫。
upd：原来有非图论做法。至少图论做法是真的逆天。
首先用数据结构维护，模拟出天降积木的过程，可以得到各块积木的上下边界的纵坐标，这部分的处理是独立的。
然后对具有 公共角 的的矩形（或地面）进行连边（可以对横纵分别考虑，双指针实现。注意建出的图不能包含重边！），容易证明边数是 \(O(n)\) 的（你可以对矩阵的四条边分别考虑）。
容易想到洞的数量与图上 简单环 的数量有一定的联系。
但这时并不能着急着将环数（以下的环数均表示简单环）当作洞数处理：比如三元环，以及如何处理四面共角。
给出一个统计的思路：数环的总数 \(\to\) 减去三元环的数量 \(\to\) 调整四面共角对正确答案的影响。
三元环计数是相对容易的，这里不赘述其 \(O(n\sqrt{n})\) 的做法。
数总环数可以使用平面图的欧拉定理：\(f + v - e = 2\)（面数 \(f\) 包含 \(1\) 个无穷平面）。注意由于存在四面共角的情况（即存在若干 \(K_4\)），原图并不能当作一个平面图，因此无法嵌入 \(S_0\) 进行考虑（也就是说，你并不能直接使用公式 \(f + v - e = 2\)）。
给一个非平面图的例子：\(2 \times 3\) 个 \(K_4\) 拼接在一起，形成 \(3 \times 4\) 的点阵。
取边长为 \(3\) 的两边的中点，再在边长为 \(4\) 的两边各取中间四个点。
如果你圈出了这 \(6\) 个点组成的六边形，你不难发现，此处有一个图与 \(K_{3, 3}\) 同胚。
我们思考这个四面共角的情况对洞数的贡献是 没有任何意义的，于是可以将 \(K_4\) 转成四元环，考察各数值的变化量。具体如下考虑：
-
记原图为 \(G\)。删掉 \(G\) 中所有 \(K_4\) 的任意两条没有公共点的边 \(e_1, e_2\)，每个 \(K_4\) 形成一个四元环。记改造的 \(K_4\) 数量为 \(c\)，变换后的图为 \(G^{'}\)。易知 \(G^{'}\) 一定为平面图。
-
考察对 \(G\) 错误使用欧拉定理计算的答案 与 对 \(G^{'}\) 正确使用欧拉定理计算的答案（即正确答案）以及 \(G\) 与 \(G^{'}\) 相关量之间的联系。
-
记原图中非 \(K_4\) 内三元环数为 \(t\)。
-
记 \(G\) 中点数为 \(v\)，边数为 \(e\)，面数为 \(f\)（错误的算法下）。错误使用欧拉定理，得 \(三元环数 + 洞数 + 1 = f = e + 2 - v \xrightarrow{三元环数 = 4c + t} 洞数ans = e - v + 1 - t - 4c\)。
-
记 \(G^{'}\) 中点数为 \(v^{'} = v\)，边数为 \(e^{'} = e - 2c\)，面数为 \(f^{'}\)（正确的算法下）。正确使用欧拉定理，得 \(三元环数 + 四元环数 + 洞数 + 1 = f^{'} = e^{'} + 2 - v^{'} \xrightarrow{三元环数 = t, 四元环数 = c} 洞数ans^{'} = e - 2c + 2 - v - (c + 1) - t = e - v + 1 - t - 3c\)。
-
我们发现：\(ans^{'} - ans = c\)。不难猜测，每一个 \(K_4\) 在错误使用欧拉定理的算法下，都会少算 \(-1\) 的代价。事实上，如果你对每个 \(K_4\) 分别考虑，确实会得到这样的结论。不妨自己想一想。
于是，四面共角的偏移量居然如此简洁：只需要在原来的错误算法上，对每个 \(K_4\) 增加 \(1\) 个贡献。
最后回到原题，要求的是每落下一块积木对洞数造成的偏移量。
对此，我们只需要把贡献累计到与对应信息相关联的点中，出现时间最晚的那个即可。
从实现角度来讲，建边的过程是最痛苦的。
P3960 [NOIP2017 提高组] 列队
P1848 [USACO12OPEN] Bookshelf G
P1856 [IOI1998] [USACO5.5] 矩形周长Picture
P4064 [JXOI2017] 加法
直接做不太会，考虑二分答案，这样每个位置至少需要加多少次就定下来了。
问题转化为：第 \(i\) 个位置至少要被覆盖 \(w_i\) 次，要求从 \(m\) 个区间中选出恰好 \(k\) 个区间进行线段覆盖，问是否存在合法方案。
然后有一个 naive 的 \(O(n\log{n})\) 想法（单次判定），每个线段的左端点挂上该线段，从左往右扫，把 \(i - 1\) 位置剩下的线段（也有可能是 \(i - 2, i - 3, \dots\) 位置为左端点的线段）继承到 \(i\) 位置，并在优先队列中按照右端点从大到小排序，每次取出队头将其覆盖，并影响到之后的位置（区间修改单点查询，这个可以用树状数组维护，常数小），直到该位置被覆盖 \(w_i\) 次，继续向后移动。
总时间复杂度为 \(O(n\log{n}\log{V})\)，居然跑得挺快。
warning：注意判断取出来的线段右端点是否 \(\ge\) 当前位置。模拟赛挂了 \(80\) 分。
P1712 [NOI2016] 区间
P5226 [SCOI2015] 小凸解密码
不要看错题了，\(B_x\) 的值只与 \(A_x\) 和 \(A_{x - 1}\) 以及 \(C_x\) 有关，题目给的并不是 \(B\) 的递推关系！所以它这个修改操作就显得非常无脑了，其实就是单点修改。
破环成链，直接用 set 暴力维护 \(0\) 区间，lower_bound 出可能成为答案的常数个区间，暴力拿出来更新。对于 \(B_0 = A_0\) 的限制，也是单点改一下就可以了，但不管这个居然能过原数据，只能说当年的数据造的是真的水。
有点细节，但都出得很没水平。感觉不如猿神。注意：
- 当左端和右端都为 \(0\) 区间时，这两段 \(0\) 区间不能单独对答案做贡献。
- 要把 \(x, x + n, x - n, x + 2 \times n\) 都拿出来和 \(0\) 区间取距离最小值，这个也不难想到。
P3587 [POI2015] POD
对 pushdown 与区间加组合起来的性质的妙妙运用。
问题容易转化为选取区间而不是截环成链。（注意 \([1, x], [x + 1, n]\) 这样的划分链方式不能被计重）
P3302 [SDOI2013] 森林
如果可以离线，那直接考虑最终的树的形态。
然后就是一个经典问题，用（以点权为下标的）主席树维护每个点到根的每种点权的前缀数量，对于询问 \((u, v)\)，记 \(lca\) 表示 \(u, v\) 的最近公共祖先，\(fa_x\) 表示 \(x\) 的父亲，则用 \(u\) 处的主席树加上 \(v\) 处的主席树减去 \(lca\) 处的主席树再减去 \(fa_{lca}\) 的主席树即可得到一条链的信息。
由于此题需要在线，所以必须考虑如何进行加边操作，而加边操作的实质是合并两棵树。由于只有加边且保证任意时刻都是森林，所以合并的总大小是定值，容易想到用启发式合并，每次将较小的那棵树 DFS 一遍再接到较大的那棵子树上。
时间复杂度 \(O(n\log^{2}{n})\)，空间复杂度 \(O(n\log^{2}{n})\)，如果使用垃圾回收可以将空间复杂度砍一只 \(\log\)。
P4137 Rmq Problem / mex
经典问题了，区间求 mex。
一开始肯定会去想用主席树维护每个数的前缀数量和，然后将两棵线段树相减即可得到区间每个数的数量信息。但问题是，这样并不方便查询。
换个思路，考虑用主席树维护每个前缀中一个数最后出现的位置 \(pos\)，则对于查询区间 \([l, r]\)，所有 \(pos < l\) 的数都不在当前区间中出现，查询最小的那个即可。
P4113 [HEOI2012] 采花
也是典题，离线之后考虑维护前驱，用树状数组支持查询前驱在 \([l, r]\) 内的数的数量。
P4197 Peaks
还是典题，带我重学了一遍 Kruskal 重构树。实际上是个非常简单的小技巧。
建出 Kruskal 重构树后，相当于询问一个子树内原节点（原节点一定都是叶子节点）的第 \(k\) 大点权。
这相当于查询 dfs 序区间（仅考虑叶节点）的第 \(k\) 大权值，直接上主席树即可。
P4121 [WC2005] 双面棋盘
P8476 「GLR-R3」惊蛰
一个显然的事情是，构造出的 \(b\) 序列中的元素一定来自于 \(a\) 序列中的数或 \(0\)。
将 \(a\) 排序过后的序列记为 \(w\)。特别地，\(w_0 = 0\)。
设计 DP 状态 \(f_{i, j}\) 表示考虑 \(b\) 的前 \(i\) 个位置，\(b_i\) 填 \(w_{j}\) 的最小代价，并记 \(g_{i, j} = \min\limits_{x = j}^{n}f_{i, x}\)。则：
然而 \(f\) 并不方便维护。但看起来可以尝试只维护 \(g\)，并且我们最后也确实可以用 \(g\) 表示答案。
我们对于 \(cost\) 的贡献分类讨论，并尝试用数据结构维护 \(g\)。
记 \(p\) 表示最大的下标使得 \(w_{x} < a_{i}\)。
对于 \(j \in [p + 1, n]\)，\(f_{i, j} = g_{i - 1, j} + w_{j} - a_{i}\)。
发掘性质：\(g_{i}\) 关于 \(j\) 单调不降，\(w\) 关于 \(j\) 单调不降，所以 \(g_{i, j} = \min\limits_{x = j}^{n}f_{i, x} = \min\limits_{x = j}^{n}(g_{i - 1, x} + w_{x} - a_{i}) = g_{i - 1, j} + w_{j} - a_{i}\)。
这样就可以摆脱掉 \(f\) 啦！
对于 \(j \in [0, p]\)，\(f_{i, j} = g_{i - 1, j} + C\)，这个直接区间加即可，然后最后把两段拼起来更新后缀最小值，注意到两段分别更新后得到的 \(g\) 都是单调不降的，所以前面被后面影响到的 \(g\) 必然是一段后缀 \([y, p]\)，其中 \(y\) 是最小的下标使得 \(g_{i, j} > g_{i, p + 1}\)。
特别提一下 \(j \in [p + 1, n]\) 中，转移式中 \(-a_{i}\) 是可以直接区间减的；\(+w_{j}\) 这件事是区间加一个序列，看起来不太好搞，但在线段树上是容易维护的：明确我们要维护的是后缀最小值的区间最大值（以二分出 \(y\)），由 \(g, w\) 单调性相同，\(+w_{j}\) 修改前后的区间最大值一定都在右端点处，因此可以记标记 \(wadd\) 表示区间 \(+w_{j}\) 操作被执行了多少次，下传标记时给区间 \([l, r]\) 内的最大值加上 \(wadd \times w_{r}\) 即可。
以上均可用线段树简单维护，实现：
-
查询后缀最小值的区间最大值。
-
区间加。
-
区间赋值。
-
区间给 \(i\) 位置的值加上 \(w_{i}\)。（注意这里能支持该操作是由于单调性的存在）
时间复杂度 \(O(n\log{n})\)。
难点在于利用单调性将 DP 式转化成容易利用数据结构维护的形式（并且发现 \(+w_{j}\) 是容易维护的）；更新 DP 值时可以考虑 先分治、再合并 的思想。
可以加深对懒标记的理解。
P7214 [JOISC2020] 治療計画
P5298 [PKUWC2018] Minimax
把牢大肘出直升机后打赢复活赛了。
典题神题套路题。
首先离散化。记 \(f_{u, x}\) 表示节点 \(u\) 的权值为 \(x\) 的概率。
对于叶节点和单个子节点的情况比较简单，以下只考虑双子节点的情况。
由于叶节点权值互不相同，则可以考虑枚举权值得到以下递推式：
考虑合并左右子节点代表的两棵树，如果在某个节点 \(v\) 对应的位置上有且仅有一棵树上非空或递归到叶节点，则可以快速得到 \(v\) 所代表的权值区间的概率。
具体地，假设已知某段权值区间的转移必为 \(f_{u, x} = f_{L, x}\left( p_{u}\times \sum\limits_{j = 1}^{x - 1}f_{R, j} + (1 - p_{u})\times \sum\limits_{j = x + 1}^{m}f_{R, j} \right)\)，则在合并时不断累加前缀和和后缀和（通过维护区间 \(f\) 和并在递归时判断递归方向即可）可以得到相同的系数，即括号内的值，而这段权值区间的概率的改变均为对应位置上乘上该系数。
通过对特殊情形的转移进行考察，从而找到总体的解决目的：维护区间 \(f\) 和。
以上特殊情形已经阐明，而一般情形也只需要将两棵已合并完成的子树的权值进行相加即可。
时空复杂度就是线段树合并的 \(O(n\log{n})\)。
P6773 [NOI2020] 命运
记 \(d_{u}\) 表示节点 \(u\) 的深度。
如果有多个以 \(u\) 为下端点的限制，则只有上端点深度最大的那一条限制是有效的，记其为 \(w_u\)，若没有以 \(u\) 为下端点的限制则 \(w_{u} = 0\)。
记 \(f_{u, i}\) 表示考虑 \(u\) 子树，下端点在 \(u\) 子树内的所有未满足的限制中上端点深度最大为 \(i\) 时的方案数。特别地，\(f_{u, 0}\) 表示所有下端点在 \(u\) 内的限制均已满足。
做树形 DP，初始化 \(f_{u, w_{u}} = 1\)，答案为 \(f_{1, 0}\)，转移讨论边 \((u, v)\) 填 \(0 / 1\)：
记 \(g_{u, i} = \sum\limits_{x = 0}^{i}f_{u, x}\)：
嗯，这很线段树合并，并且这个前缀和 \(g\) 的处理方式与 P5298 [PKUWC2018] Minimax 是一样的。
那就没什么好说的了。
tips：注意写法问题，特别是只代表一个权值的节点时，可能没有把该点的 \(f\) 值累加到系数中。而 P5298 [PKUWC2018] Minimax 由于不会递归到 \(l = r\)，因此不会出现这种问题。
P3293 [SCOI2016] 美味
从高位向低位贪心地确定 \(a_i + x\) 整体的值，讨论当前位能否填与 \(b\) 相异的数，这样可以确定出合法 \(a_i\) 的范围，用主席树维护 \(a\) 的数量，查询合法值域内是否在当前区间中至少存在一个元素，如果有就可以直接贪心地将 \(a_i + x\) 的当前位填上与 \(b\) 相异的数。
时间复杂度 \(O(Q\log{V}\log{n})\)，比较简单的一道题。
P7518 [省选联考 2021 A/B 卷] 宝石
然而并没有用到 DS。
为了方便描述，首先可以将点权 \(a\) 改成其对应在 \(p\) 数列上的排名（\(p\) 中元素互不相同）。
记 \(s, t\) 为路径的起点与终点，\(lca\) 表示二者的最近公共祖先。
显然可以把路径拆成 \(s \to lca\) 和 \(lca \to t\) 两部分。
我们先考察向上跳最多能取多少个宝石：显然是遵循能取就尽量取的原则。
维护 \(nxt_{u, i}\) 表示以节点 \(u\) 为开头，向上选取 \(a_{u}, a_{u} + 1, \dots, a_{u} + 2^{i} - 1\) 后所到达的最近点。则第一步先向上跳到最近的 \(1\)，之后直接利用倍增数组 \(nxt\) 即可。
对于向下跳，直接处理是不太好做的，但可以逆向考虑宝石的选取。假如最终选取了 \(m\) 个宝石，那么先选 \(m\)，再选 \(m - 1\)...这个过程同样可以用上述的倍增过程找到以 \(m\) 开头的最长连续下降子序列，类似地维护 \(pre_{u, i}\) 表示以节点 \(u\) 为开头，向上选取 \(a_{u}, a_{u} - 1, \dots, a_{u} - 2^{i} + 1\) 后所能到达的最近点。用第一步向上跳到最近的 \(m\)，之后利用倍增数组 \(pre\) 即可。
然后 \(m\) 是最终的答案，稍加思索便可以发现这是可以二分的，所以二分答案后做倍增判断 \(s \to lca\) 与 \(lca \to t\) 是否可以拼起来即可。
时间复杂度 \(O(n\log{m} + q\log^{2}{m})\)。
important tips：向上跳的第一步如何处理捏？将询问离线分别到 \(s, t\)，做两遍 dfs（先 \(s\) 后 \(t\)）维护当前节点往上每种颜色的最深位置，由于每次移动只会改变一个元素的信息，因此这是容易的。然后就可以不借助线段树等 DS 优雅地解决这道题。
gossips：居然过编后一遍过了，很开心。