本文章由 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

红黑树的性质

• 每个节点或红或黑
• 根节点是黑色的
• 叶节点是黑色的
• 红节点的孩子是黑色的
• 某子树上根到叶子节点的简单路径上经过的黑色节点数相等，并将此量设为 $\text{bh}(x)$。

（注意这里的叶子节点是指没有权值的哨兵）

我们先证明红黑树的平衡性，即，红黑树的高度是 $O(\lg (n+1))$ 的。

引理 1 以 $x$ 为根的子树，大小至少为 $2^{\text{bh}(x)} - 1$。

用归纳法进行证明。

• 当 $x$ 是叶子节点时，显然成立。
• 否则，以 $x$ 为根的子树的大小为：$2\times (2^{\text{bh}(x)-1} - 1) + 1 = 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)$。

红黑树的插入

红黑树的插入，需要维护它的一些性质。我们按照普通二叉搜索树的方式插入，并将新节点标记成红色（因为处理黑高很麻烦），然后考虑哪些性质可能被违反：

• 性质 1：不违反
• 性质 2：如果新插入的节点就是根，那么违反
• 性质 3：不违反
• 性质 4：如果父节点是红色的，那么违反
• 性质 5：不违反

性质 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$ 无孩子，直接删除
• 若 $x$ 只有一个孩子，那么将此孩子提升到 $x$ 的位置
• 否则，找 $x$ 的后继，设为 $y$。当 $y$ 不是 $z$ 的直接右儿子时，我们以 $y$ 的右儿子替换它。之后，我们用 $y$ 替换 $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

Complete The Graph

• 枚举：每次将为零的边加上 $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$。

P2149 [SDOI2009] Elaxia的路线

对每一个源点和终点跑一遍最短路，然后建出一个由 $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)$$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-16 10:40:03

挺简洁的，效率也不错。去掉类模板 78 行。

template<typename T, size_t N> class SplayTree
{
private:
    T val[N];
    int son[N][2], fa[N], siz[N], cntq[N], cnt = 1, rt = 0;
    
    void maintain (int x)
    { siz[x] = siz[son[x][0]] + siz[son[x][1]] + cntq[x]; }
    int get (int x) const { return son[fa[x]][1] == x; }
    int compare (int f, T k) const { return k > val[f]; }
    void rotate (int);
    int splay (int f, int t = 0);
    int search (T k);
    int insert_at (int f, T k) {
        cntq[cnt] = siz[cnt] = 1, val[cnt] = k, fa[cnt] = f;
        if (f) son[f][compare (f, k)] = cnt;
        return cnt++;
    }
    int merge (int x, int y);
public:	
    int insert (T k);
    int remove (T k);
    int qrank (T k) { return siz[son[search (k)][0]] + cntq[rt] * (val[rt] < k); }
    T kth (int k);
    T qpre (T k);
    T qnext (T k);
};

template<typename T, size_t N>
void SplayTree<T, N>::rotate (int x)
{
    int y = fa[x], z = fa[y], p = get (x);
    son[y][p] = son[x][1 ^ p];
    if (son[x][1 ^ p]) fa[son[x][p ^ 1]] = y;
    son[x][p ^ 1] = y, fa[y] =  x, fa[x] = z;
    if (z) son[z][y == son[z][1]] = x;
    maintain (y), maintain (x);
}

template<typename T, size_t N>
int SplayTree<T, N>::splay (int x, int t)
{
    for (int f = fa[x]; (f = fa[x]) != t; rotate (x))
        if (fa[f] != t) rotate (get (x) == get (f) ? f : x);
    return t ? x : rt = x;
}

template<typename T, size_t N>
int SplayTree<T, N>::insert (T k)
{
    int f = rt, last = 0;
    if (!f) return rt = insert_at (0, k);
    while (f && val[f] != k) last = f, f = son[f][compare (f, k)];
    if (f && val[f] == k) return cntq[splay (f)]++;
    else return f = insert_at (last, k), maintain (last), splay (f);
}

template<typename T, size_t N>
int SplayTree<T, N>::merge (int x, int y)
{
    int f = x;
    if (!x || !y) return x + y;
    while (son[f][1]) f = son[f][1];
    splay (f, fa[x]);
    if (y) fa[y] = f;
    son[f][1] = y;
    return f;
}

template<typename T, size_t N>
int SplayTree<T, N>::remove (T k)
{
    int f = search (k), x;
    if (cntq[f] > 1) return cntq[f]--, f;
    if ((x = merge (son[f][0], son[f][1]))) fa[x] = 0;
    return rt = x;
}

template<typename T, size_t N>
T SplayTree<T, N>::kth (int k)
{
    int f = rt;
    while (f)
        if (k <= siz[son[f][0]]) f = son[f][0];
        else if (k <= siz[son[f][0]] + cntq[f]) return val[splay (f)];
        else k -= siz[son[f][0]] + cntq[f], f = son[f][1];
    return 0;
}

template<typename T, size_t N>
T SplayTree<T, N>::qpre (T k)
{
    int f = son[search (k)][0];
    if (val[rt] < k) return val[rt];
    while (son[f][1]) f = son[f][1];
    return val[splay (f)];
}

template<typename T, size_t N>
T SplayTree<T, N>::qnext (T k)
{
    int f = son[search (k)][1];
    if (val[rt] > k) return val[rt];
    while (son[f][0]) f = son[f][0];
    return val[splay (f)];
}


template<typename T, size_t N>
int SplayTree<T, N>::search (T k)
{
	int f = rt;
	if (!f) return 0;
	while (son[f][compare (f, k)] && val[f] != k)
		f = son[f][compare (f, k)];
	return splay (f);
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-16 13:32:16

首先我们有

$$\sin (\lpha + \beta) = \sin\lpha \cos\beta + \sin\beta \cos\lpha$$

于是维护区间正弦和以及正切和即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-20 15:21:09

快速排序是一种不稳定的通用排序算法，也是应用最为广泛的排序算法之一。它有着 $O(n\lg n)$ 的优秀期望复杂度（众所周知，排序的最优复杂度就是 $\Omega(n\lg n)$ 的）。

同时，对比一般的归并排序，它是原地的，空间复杂度 $O(1)$。唯一美中不足的是它不稳定，即，它会交换两个相同的元素顺序。因此如果对稳定性有需求，还是需要使用稳定的归并排序。

快速排序的思想很简单：取一个元素记作 $p$，然后将序列分为两部分，一部分严格小于 $p$，另一部分大于等于 $p$，然后在这两部分上递归。到达单元素序列回溯。

关键在于怎么选这个 $p$。朴素的快速排序总是选择序列的第一个或者最后一个元素，但是在一些极端情况会被卡掉：全部是一个元素的序列，与本来就有序的序列。

我们需要进行优化。显然，我们希望 $p$ 的选择接近原序列的中位数。这样，我们就可以将原序列划分为两个长度相同的序列，达到 $O(n\lg n)$ 的复杂度。问题在于如何选择这样的 $p$。

其实很简单，可以在选取序列头尾以及中间的三个数的中位数，或者取随机值。在本题中，随机值比三数取中跑得快 9 ms。

实际上，std::sort 用的是内省排序（introsort），它本质也是一种快速排序，但是在序列较短的时候采用插入排序，在递归栈太深的时候采用堆排序。工业用的大多数通用排序算法大多也基于此。