本文章由 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），它本质也是一种快速排序，但是在序列较短的时候采用插入排序，在递归栈太深的时候采用堆排序。工业用的大多数通用排序算法大多也基于此。

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

赛后诸葛亮系列。思路还是不够开。

赛时写了一堆模拟，最后发现越来越复杂。事实证明，ABC 从来没有复杂的模拟题，只有你想不到的思维题。

实际上用 DP 很自然就能做出来。$f(i)$ 为到前 $i$ 个元素正着的最高点，$g(i)$ 为反过来。我们要找的是正反的交汇点，也就是 $\min \{f(i), g(i)\}$。

然后我们考虑转移。很明显，对点 $i$，如果 $s_i \ge f(i-1)$，那么 $f(i)\gets f(i-1)+1$。否则，山在这里就断了，$f(i) \gets s_i$。$g()$ 同理。

最后取 $\min \{f(i), g(i)\}$ 的最大值。

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

本题实际上和删边最短路差不多，都是考察对算法的理解。只不过这题是考察 Floyd，而我的删边最短路是考察 SPFA（其实我本来想把它做成一个 DP 题）。

已知每一个点的修建完成时间，实际上这就是每一个点的建立顺序。给定了一个时间，我们就知道存在哪些点，进一步知道我们可以用哪些边来组成这个最短路。

然后就很简单了。对于每次询问，我们找 $t$ 时间内可以修建完成的点，然后用这些点来进行部分的 Floyd：即将最外层的 $k$ 换成一个定点。然后就能得到 $u$ 到 $v$ 的最短路。

需要进行的检查是：因为进行 Floyd 时，所有能用的点已经是前面询问得到的，因此一定都是在当前时间前的（题目给定 $t$ 单调不降）。于是我们只需要检查 $u$ 与 $v$ 现在修建完了没。

看来删边最短路也能评绿了（

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

P4316 绿豆蛙的归宿

题意比较简单：走到每一条边的概率是起点的出度分之一，保证图联通无环，求路径总长度的期望。

这是一个简单的图上拓扑 DP。只需要设 $f(v)$ 代表走到点 $v$ 的概率，于是 $f(v) = \dfrac {f(u)}{d^+(u)}$。于是明显，走到边 $(u, v)$ 的概率就是 $\dfrac {f(u)}{d^+(u)}$。

由于图是联通且无环的，我们统计总和即可。

CF1131D Gourmet choice

题意就是：给定了 $a_i$ 与 $b_i$ 之间的关系，求最小可能的 $a$ 与 $b$ 序列。

利用拓扑排序解决问题的关键在于找出顶点之间的关系与限制，然后用拓扑排序取得一个可行解。在这个问题中，很明显，限制就是元素之间的大小关系。

但是需要处理相等的情况。很明显，可以用一个并查集将相等的元素合并起来，因为无论怎么样，这些数的最终取值都是相等的。

之后一遍拓扑即可。

CF1635E Cars

我们可以想到：两量方向向外的车，一定无关紧要；同理，两辆命中注定的车，一定共同指向内端。再考虑方向：根据上面的方案，不管两辆车是无关紧要还是命中注定，它们方向都相反。我们可以简单的设 $1$ 号车的方向向左，然后染色即可。

之后我们建图。其实可以用原图来删边，省空间，不过逆向思维不好想。

P3243 [HNOI2015] 菜肴制作

如果没有限制顺序的要求，简简单单拓扑就行了。但是这个限制没有看起来那么简单：要求的是编号小的尽可能往前，但这并不是说字典序尽可能小。考虑 $2314$ 和 $3124$，前者的字典序更小，但后者才是题中说的更优的。

那这怎么处理？把它翻转过来：我们要求小元素尽量靠前，反过来就是小元素尽量靠后，也就是大元素尽量靠前，这实际上就是说字典序最大。那么原来的要求反过来是什么？是说编号大的尽可能往后，是句废话，没法转化。

所以我们要做的就是建反图，用优先队列让大编号点尽可能往前，然后取逆序列。

CF1100E Andrew and Taxi

题意（翻译）极其简洁。既然要 “最大值最小”，很明显二分。于是将最优化转化成可行性判定：是否能通过改变边权小于等于 $k$ 的边来使图变为有向无环图。

我们知道：如果不限制边权，那么一定能将一个图转化为无环图。方法如下：我们找到图中入度最小的点，把它的所有入边改成出边，这样就能让它脱环。将它删除后，对剩余图进行同样的操作。

于是我们知道：只要是由边权大于等于 $k$ 的边组成的图无环，我们就一定能仅仅通过改变边权小于 $k$ 的边，将这个图转化为无环的。判断有环是简单的，可以用拓扑，也可以用 DFS。

最后的问题就是怎么求方案。实际上也简单。我们对由边权大于等于 $k$ 的边组成的子图进行拓扑排序，得到每个点的拓扑序。然后对剩下的每一条边，使起点的拓扑序小于终点，否则改变方向。注意我们并不求改变方向的最少次数。

总结

拓扑排序有两种题：图上 DP 与求限制方案。对于前者，实际上动态规划转移的过程就是在 DAG 上遍历。点就是状态，而边就是转移。我们设出点代表的状态，然后来找与此相关的边的转移。

对于后者，重要的是找到边的方向以及权值代表的实际意义。这需要我们理解拓扑的原理：起点在拓扑序中，一定在终点之前。通过这个原理，我们就能排出方案。

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

如果没有这个 $k$ 的限制，本题可以降黑了（大雾）

可以用 DP 做，但因为 DP 本身就是 DAG 的一种其他形式，我们可以直接建一个新图。具体的，将原来的 $n$ 个点变为 $kn$ 个，每一个点 $jn+i$，代表使用 $j$ 张免费票时的点 $i$。再找边：由 $(j - 1)n + u$ 可以以零边权指到 $(j - 1)n+v$，由于无向，反着指也可以。同时，$jn+u$ 和 $jn+v$ 是以 $w$ 边权联通的，其中 $w$ 就是正常机票。

之后我们要求的就是 $s$ 到 $jn+s$ 的最短距离，$\text{s.t.} \space j \in [0,k]$（这是一个坑点）。这个题开空间也是个坑点，让我爆了好几遍紫。。

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

本题题意明显，就是求次短路。

最开始的思路比较简单：找出最短路，删掉这些边，然后再跑一次最短路，但这也很明显是错的。

实际上，我们可以像维护最短路那样，维护一个次短路。设 $f(v)$ 是从源点出发到点 $v$ 的最短路，$g(v)$ 则是相同意义下的次短路。

对于每次在边 $<u, v, w>$ 上的松弛操作：

• 若可以更新最短路，即 $f(v) \gt f(u) + w$，那么 $g(v) \gets f(v)$，$f(v) \gets f(u) + w$

• 若最短路没法更新，但是可以用原最短路更新次短路，即 $f(v) \le f(u) + w$ 但 $g(v) \gt f(u) + w$，那么只更新次短路：$g(v) \gets f(u) + w$

• 如果能更新次短路，即 $g(v) \gt g(u) + w$，那么 $g(v) \gets g(u) + w$

上述三个操作是依次进行的。这样进行一次 SPFA 就可以了。

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

其实就是找 $x$ 到 $y$ 上的边权最小值的最大值。

那么我们可以考虑建一个最大生成树，然后在上面用倍增（LCA）来取边权的最小值。容易证明，在这个最大生成树上的边权最小值，一定是可能的最大值。

建最大生成树的过程实际上和最小生成树的贪心策略是一样的（Kruskal），只是排序反过来。

LCA 的特殊之处在于需要维护一个最小值的倍增。

别的就是板子了。以上。

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

考虑到我们可以枚举中间值，然后要求的就是在每个元素之前，小于这个元素以及大于这个元素的元素数量。用乘法原理即可得到最后答案。

形式化地，我们设 $l_i$ 是 $1$ 到 $i - 1$ 中小于 $x_i$ 的元素数量，$r_i$ 对称，那么最终答案就是 $\sum\limits_{i=1}^{n} l_i\times r_i$。

那么我们就是要求参数 $l_i$ 与 $r_i$。考虑离线 + 离散化 + 树状树组。这里树状树组实际上就是个桶前缀和。

然后做法明显。