ryp 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-08 16:55:52
分数规划，$\dfrac{\sum\limits_{u \in S} F_u}{\sum\limits_{e \in E} T_e} \ge c$，即 $\sum\limits_{u\in S} F_u \ge c\sum\limits_{e\in E} T_e$，即 $\sum\limits_{u\in S}F_u - c\sum\limits_{e\in E}T_e \ge 0$，即 $\sum\limits_{e\in E} cT_e - \sum\limits_{u\in S} F_u \le 0$
于是就变成判断负环，其中，每一条边 $(u,v)$ 的边权就是 $cT_e-F_u$。
用 SPFA + 二分可做。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-09 13:04:55
排列 DP 的一般状态是：$f(i, j)$ 代表 $1$ 到 $i$ 的排列中，目标组合已经有了 $j$ 个。
那么套用到本题就是：$f(i, j)$ 代表 $1$ 到 $i$ 的排列中，已经有了 $j$ 个逆序对。
我们很容易注意到，由于 $i$ 在 $1$ 到 $i - 1$ 的排列中是最大的，我们无论将 $i$ 插入到哪里都会让整个序列的逆序对数量加上这个位置后面的数字数。
形式化地，设 $i$ 被插入到 $p$ 的位置，其中 $p\in [0,i - 1]$，那么，逆序对将会比原来多 $i - p - 1$ 个。也即，$f(i, j) = \sum\limits_{p=0}^{i-1}f(i-1, j - i + p + 1)$。规约一下，得到
$$f(i, j) = \sum\limits_{k=\max{0,j-i+1}}^{j} f(i-1, k)$$
这个转移就是 $O(n)$ 的，于是整体 $O(n^2k)$，显然不行。
我们考虑：等号右边是一个求和，而且求和区间随着 $j$ 的移动而单增。那么，我们可以维护一个前缀和。
我们维护 $\sigma(j) = \sum\limits_{k=0,j-i+1}^j f(i-1,k)$，那么在转移的时候，有 $f(i,j) \gets \sigma(j)$，随后 $\sigma(j)$ 更新上 $f(i, j)$ 的值。
此时如果 $j - i + 1$ 移动，我们就需要减去移动的这一段空窗，即 $f(i - 1, j - i + 1)$。
典型的黄题比绿题难……
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-10 17:50:00
本题的转移方程显然
$$f(i) = \max\limits_{0 \le j \lt i} f(j) + 1, \space \text{s.t.} \space \max a_j \le \min a_i$$
如果没有后面的限制，这玩意儿就根本不是个动态规划，因为我们可以证明此时 $f(i) = f(i-1) + 1$。但是有了后面的限制之后，问题棘手了一些，因为转移变成了 $O(n)$ 的，难以接受。
我们可以考虑 CDQ 分治：先对左区间进行处理，然后考虑对右边的影响。只考虑影响的时候，由于本题显然有单调性，我们可以将左右区间排序，左区间依据 $\max a_i$，右区间依照 $a_i$。
这样，我们用双指针（CDQ 分治标配）扫描一边，利用单调性，可以做到 $O(n\lg n)$（$\lg n$ 来自树状树组）。加上排序 $o(n\lg n)$，整体复杂度是 $O(n \lg^2 n)$，不错。
总体上看，CDQ 分治首先利用分治的思想，让我们只需要考虑左区间对右边的影响（因为左边与右边单独的两个区间，是另外的两个问题）。这个时候，我们就可以利用问题的单调性，加上双指针与一些数据结构（常见树状树组）就能解决问题。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-12 16:13:57
本题用到的是一个简单的技巧：在一棵树上，我们可以将边权转化为更深那个点的点权。
没了。
另外树剖一遍过是真爽！
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-12 22:05:45
设 $\sigma(i)$ 是某个点属性 $f(i)$ 从根到 $i$ 路径上所有点的前缀和，那么
$f(i, j) = \sigma (i) + \sigma(j) - \sigma(x) - \sigma (y) $，其中 $x$ 是 $i$ 与 $j$ 的 LCA，$y$ 是 $x$ 的父节点。
推导画图显然。
没了。
（感觉现在写 blog 越来越糊弄……）
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-13 16:40:16
首先我们有一个朴素转移：设 $f(i)$ 表示给前 $i$ 个珍珠上色完的最少点数，那么 $f(i) = \min\limits_{0\le j \le i} f(j) + \sigma^2(j+1,i)$，其中 $\sigma(i, j)$ 表示 $[i, j]$ 的不同颜色数。
这个转移是 $O(n^2)$ 的，我们考虑怎么优化。我们注意到：对于一个区间 $[l, r]$，我们存在平凡涂色方法，即一个一个涂色，这样的代价是 $r - l + 1$，即区间长。那么我们知道，每一个有意义的 $f(i) \le i$，于是 $\sigma(j+1,i) \le \sqrt i$，于是 $j + 1 \le \sqrt i$。我们可以直接认为 $j \le \sqrt i$，那么就变成了在 $[\sqrt i, i]$ 上枚举最小的 $j$。
最终的转移方程是：
$$f(i)=\min\limits_{\sqrt i\le j\le i} f(j)+\sigma^2(j+1,i)$$
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-13 21:39:07
首先离线，将时间抽为第三维，然后我们考虑每一次的删除会导致逆序对减少多少。
我们设每个点的第一维 $x_i$ 为它被删除的时间（或正无穷），第二维 $y_i$ 是它的下标，第三位 $z_i$ 是值，那么一个点 $p$ 被删除后，逆序对减少的数量，就是使得 $x_p \le x_q, \space y_p \lt y_q, \space z_p \gt z_q$ 或者 $x_p \le x_q, \space y_p \gt y_q, \space z_p \lt z_q$ 的 $q$ 的数量。
于是我们的问题就变成了三维偏序：先算出初始的逆序对数量（这时候是个二维偏序），然后统计在每一个时间上上面两个偏序的总数量，相减即可。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-14 21:50:47
（注意这里的叶子节点是指没有权值的哨兵）
我们先证明红黑树的平衡性，即，红黑树的高度是 $O(\lg (n+1))$ 的。
引理 1 以 $x$ 为根的子树，大小至少为 $2^{\text{bh}(x)} - 1$。
用归纳法进行证明。
证毕。
引理 2 以 $x$ 为根的子树到其任意叶子节点的简单路径上，至少有一半的节点是黑色的。即，$\text{bh}(x) \ge \dfrac h 2$
结合性质 4，显然得证。
红黑树的平衡性证明 结合引理 1、2, 可知一棵 $n$ 个节点的红黑树，有 $n \ge 2^{h/2}-1$。取对数得到：$h \le 2\lg (n+1)$，即 $h = O(\lg (n+1)$。
红黑树的插入，需要维护它的一些性质。我们按照普通二叉搜索树的方式插入，并将新节点标记成红色（因为处理黑高很麻烦），然后考虑哪些性质可能被违反：
性质 2 的违反是边界情况，我们先考虑维护性质 4。
下面是平衡树标准的繁杂分类讨论……
我们设当前新加入的节点为 $x$，父节点为 $y$，叔节点（即它父亲的兄弟节点）为 $z$，祖父节点为 $p$，并以 $c(x)$ 引用 $x$ 的颜色，$0$ 为黑色，$1$ 为红色，那么已知：$c(x) = 1$，$c(y)=1$，$c(p) = 0$：
$c(z) = 1$，此时比较简单。我们使得 $c(y) \gets 0, c(z) \gets 0, c(p) \gets 1$，我们证明所有性质（在子树 $p$ 上）成立：在子树上，原来 $x, y, z$ 全部为红，现在在 $y, z$ 变黑，每条路径上黑高增加 1，保持性质 5。
$c(z) = 0$，且 $x$ 与 $p$ 同向，那么我们对 $y$ 进行以此旋转，使得 $y$ 变成新的子树根。然后，我们使 $c(y) \gets 0 , c(p) \gets 1$。此时我们来证明红黑树性质成立：相比于原来，我们的黑高仍然只增加了 1，保持性质 5。
$c(z) = 0$，且 $x$ 与 $p$ 异向。我们此时对 $x$ 进行以此旋转，然后使得 $x \gets y$，便转化到上一种情况。
我们具体分析一下。
对于一个新加入的叶子节点，它可能面临哪些情况？
首先，当一个新的节点的父亲是红色的时候，我们知道：它一定没有兄弟节点。否则，它的兄弟 $w$ 一定是黑色的。那么，显然 $y$ 子树上黑高不平衡。得证。
否则，如果它的父亲是黑色的，那么这时候不违反任何性质。
于是我们知道，当最开始进入 fixup 过程的时候，一定是面临第一种情况。
很多人说红黑树的删除很恶心之类，但实际上和插入是一个原理，只需要分类讨论即可。
我们先按普通二叉树的删除方法来删除节点 $x$。具体即：
我们记录 $x$ 原来的位置被哪个点替代，设做 $z$。我们知道，如果 $x$ 只有一个孩子，那么它一定是黑色的，删除它一定会导致这个子树上黑高变少。而当 $x$ 有两个孩子的时候，黑高的变化依赖于替代它的节点的颜色。如果这个节点是红色的，那么它的父亲是黑色的，于是 $x$ 的左子树上一定有一单位黑高用来平衡。于是，我们将 $y$ 移动到 $x$ 的位置不会影响黑高。
否则当这个节点是黑色的时候，我们推不出来什么，需要进行平衡。
下面是具体的平衡方法。我们设 $x$ 为 $x$ 原来位置上现在的节点，即 $y$ 或 $x$ 唯一的那个儿子。设 $y$ 是 $x$ 的父亲，$z$ 是 $x$ 的兄弟，$\lpha$ 和 $\beta$ 分别是 $z$ 的两个子节点。
我习惯把边界条件放在前面。$c(z) = 0$ 且 $c(\beta) = 1$ 时，这时我们旋转 $z$，并 $c(z) \gets 1, c(y) \gets 0, c(\beta) \gets 0$。此时整个子树的左边多了一个黑色，右边仍然是一个黑色，平衡，达到边界。
同样 $c(z) = 0$，但 $c(\lpha) = 1， c(\beta) = 0$ 时，我们旋转 $\lpha$，并使 $c(\lpha) \gets 0, c(z) \gets 1$，转化到前一种情况。
$c(z) = 0$，而 $c(\lpha) = c(\beta) = 0$ 时，此时我们没法从兄弟那里抢一个黑节点过来，只好上升。将 $z$ 改成红色让 $z$ 子树减少一个黑高，然后 $x$ 上升到 $x$ 的父节点。这是唯一一种需要改变 $x$ 位置的情况。
$c(z) = 1$，我们也没法直接得到一个黑节点，但可以转化下去。我们旋转 $z$，并使 $c(y) \gets 1, c(z) \gets 0$
经过以上的情况，我们便可以平衡原子树上缺少的黑高，保持了红黑树的性质。
以上。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-15 08:57:51
枚举：每次将为零的边加上 $1$，可以证明总有一个时刻最短路为 $L$。显然有单调性，二分即可。
两边 Dijkstra：先把全部零边设成 $1$，然后跑一边最短路，设 $D = L- f(t)$。$D < 0$ 时显然无解。然后跑第二遍最短路，在跑的过程中，如果对于边 $(u, v)$ 如果有 $g(u) + w \lt f(v) + D$，就让 $w \gets f(y) + D - g(x)$。
上述方法实际上将所有 $s$ 到 $t$ 上的有零点的路径长度都改成了 $L$。
对每一个源点和终点跑一遍最短路，然后建出一个由 $s_1$ 到 $t_1$ 的最短路 DAG。之后在这个 DAG 上跑一次拓扑，找最长的同时是 $s_2$ 到 $t_2$ 的最短路的边。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-15 14:55:29
设三个点为 $a, b, c$，$x =\text{lca}(a, b), y = \text{lca}(b, c), z = \text{lca}(a, c)$，不妨设 $x = y$，那么总距离为：
$$ d(a) - d(x) + d(b) + d(c) - 2 \times d(z) + d(z) - d(x) $$
整理得
$$d(a) + d(b) + d(c) - 2\times d(x) - d(z)$$
也即 $$d(a) + d(b) + d(c) - d(x) - d(y) - d(z)$$
鲁ICP备2025150228号