第十课

A - 两个团伙

经典的种类并查集。有两个做法。

  1. 用带权并查集标记奇偶性来判断与父亲的关系，比如说奇数表示不同的团伙，偶数表示相同的团伙，路径压缩的时候需要把路径上所有的关系求和，得到正确的关系后与根相连。这样查询的时候只需要判断奇偶性就行了。
  2. 用 $x$ 和 $x+n$ 表示两种团伙，如果 $x$ 和 $y$ 不在同一个团伙，那么就让 $x \rightarrow y+n$ 和 $y\rightarrow x+n$ 表示他们不在同一个团伙；这样的话查询的时候优先判断 $x$ 和 $y+n$ 在不在一个集合，如果在就说明不在一个团伙；然后判断 $x$ 和 $y$ 在不在一个团伙，如果在就说明在一个团伙；否则就是没有任何关系，无法判定。

这两个做法都比较经典比较简单。

B - 区间和探测

维护区间信息，这里就需要用到权值约束的并查集。

我们可以参考前缀和的思路。

对于一个约束 $l, r, v$ 我们可以把 $r$ 接入到 $l-1$ 来维护。首先不提怎么维护，这样做的意义是什么呢？第一个就是前缀和，因为我们要知道这里带权并查集维护的元素含义是 $sum[u]$ 表示在真实的数组中 $S_u-S_{fa}$ 的值，而按照前缀和计算区间值的方式，确实应该是要把 $r$ 连到 $l-1$ 来维护的。第二原因我们可以看向样例：

1
2
3
4
5
6
10 5
1 10 100
7 10 28
1 3 32
4 6 41
6 6 1

他告诉我们 $1\sim 10$ 的总和是 $100$，然后说了 $7\sim10$ 的和是 $28$、$1\sim3$ 的和是 $32$ 。那么用脚趾都能算出来 $4\sim 6$ 的和是 $40$ 而不是 $41$；如果我们每次只连接 $l$ 和 $r$ 的话，到了 $4\ 6\ 41$ 这一个约束并查集甚至没有把他们关联在一起，更别提找出错误了。

接下来考虑如何维护。

因为序列有自己的顺序，我们肯定是把 $r$ 的父亲设为 $l-1$，接下来的问题就是如何设置 $sum$ 的值。首先并查集肯定会找到 $r$ 和 $l-1$ 的根，我们分别设其为 $tr$ 和 $tl$，根据题目给的信息我们有以下两个等式：

这里 $sum[r]$ 表示跟新前的值，$sum[r]’$ 表示跟新后的值。因为带权并查集会在路径压缩的时候对于 $sum$ 求前缀和然后直接压到根的位置，所以我们这里只需要把 $sum[tr]$ 设为正确的值，$sum[r]$ 就会算出正确的答案。把一式代入二式再移项就可以得到 $sum[tr]$ 的正确公式：

判断约束的时候，如果 $l-1,r$ 在同一个集合内，直接判断 $sum[r]-sum[l-1]$ 的差值是不是 $v$ 即可。

C - 字母序重排

很简单，直接比较相邻的两个字符串的第一个不同字符，用一条边相连表示其中一个小于另一个。如果连出来的图是一个有向无环图，那么久一定可以找出这样一个顺序。

另外如果有形如：

1
2
aaaa
aa

这种前缀完全一样，但是排在前面的比排在后面的长的，也是 Impossible 的情形。

D - 最短路径

Dijkstra 模板题。

E - 飞行路线

这种需要在求最短路/最长路的同时还要维护其他元素的，一看就是分层图。

直接分层建图完事了。答案就是直接使用 $k$ 次免费航班那一层图的终点即可。

F - 团间距离

注意到没法建立 $k*k$ 条边，所以改变图的结构，建立一个虚点 $P$，前 $k$ 个节点直接向它连边边权为 $X$，然后再由它向前 $k$ 个节点连边，边权为 $0$，这样可以用更少的边达到了同样的效果。然后就用 Dijkstra 计算出单源最短路即可。

G - 最小整数集合

差分约束模板题。

首先介绍差分约束，如果有若干条 $a_i-b_i\ge c_i$ 的约束条件。那么就可以把它变为 $a_i\ge b_i+c_i$ 的形式，发现他特别像图论中求最短路的 Floyd 算法或者 Dijkstra 算法的松弛操作即 $dis[v]\ge dis[u]+wt$，所以不妨将其看成 $b_i$ 向 $a_i$ 连一条权值为 $c_i$ 的单向边。

这样就转化为了最短路问题。

看到这道题，发现题目给的若干个约束确实和差分约束很像。但是有一个问题，如何保证图联通呢？

我们设 $S$ 表示 $[0,i]$ 的和，然后以前缀和的方式处理出约束条件为：

但是题目中 $a_i$ 是可以为 $0$ 的，这样会非常的不方便，所以考虑把 $a_i,b_i$ 全部加一即可。

但是这样图是有可能不连通的，发现隐藏条件，一个位置最多有一个元素。即：

用这三个条件建图即可。

H - 最短路径计数问题

在求最短路的同时把最短路和次短路的数量算了即可。最后看看次短路是否比最短路刚好多一。

但是这时候要注意，因为我们同时求的次长路和路径数量，就可能让次长路成为计数的可能，所以说优先队列里同样要存储每次更新的次长路。

I - 树上找点

因为最终会对答案造成贡献的是较小边，所以考虑按照边权从大到小计算。

然后我们用并查集维护。并查集的根表示答案。这样的话可以快速计算出合并两个并查集时的最大收益。

然后模拟即可。

J - 最小环

Floyd 的外层循环的含义是只使用 $1\sim k$ 的节点时，$i$ 到 $j$ 的最短路径。所以说可以借助这个性质来使得枚举的环是简单环。

那么这样就结束了。

第十一课

A - 平面最近点对问题

考虑分治。设左边的最近点对和右边计算的答案中的较小值为 $ans$，接下来考虑合并左右两边的答案。

我们发现对于一个点来说，如果它能够跟新答案，就说明以它为圆心半径为 $ans$ 的圆内有其他的点。

有了这个性质，我们就只需要找到以他为中心左右和下方各延展 $ans$ 的矩形内的点即可。

B - 篱笆涂色

如果需要横着刷，就先横着把能覆盖整个区间的刷了，然后对于剩下的部分分治求最小值；如果不要横着刷，每个都竖着的代价是区间的大小。这两个方案取最小值即可。

C - 最大值之和

每次找到一个区间中的最大值的位置，那么它可以统治这一段区间，答案计算很简单，直接在他的左侧选择一个左端点（包括自己）然后再在右侧选择一个右端点（也包括自己），这就是他统治的所有区间的数量，乘以他自己的值即可。

如何找到最大值成了问题。

因为我们会注意到如果 $O(n)$ 的查找最大值，就会导致如果序列是递减的话，每次只会排除掉一个元素，复杂度退化到 $O(n^2)$，所以考虑优化，因为这个序列不会被修改，所以考虑倍增即可。

$st[i][j]$ 表示 $[i,i+2^j-1]$ 区间中最大值的坐标，转移很简单了。

没有细节。

D - 排列图

对于区间类型经行分类讨论：

  1. 左右端点都是极值：直接跳
  2. 左右端点都不是极值：走不了
  3. 左右端点有一个是极致，那么一定可以找到另外一个极值 $k$ 然后两个极值互联，剩下的地方递归。

做法就是对于整个区间找出最大值的位置 $k$ 以后分别处理 $1\sim k$ 和 $k\sim n$ 的两个区间，按照上面的规则递归即可。

E - 地图构建

如果用 $a_x=y$ 把一个二维的图压成一维，那么一个 $k*k$ 的矩形内恰好有 $k$ 个行列互不相同的元素的含义就是在一个长度为 $k$ 的区间中用拥有 $k$ 个连续元素的数量。

有一个经典结论就是 $mx-mi+1=len$ 的情况下，那么这一段区间内有 $len$ 个连续元素。分治统计这个数据即可。

分类讨论四种情况：

  1. 最大最小都在左
  2. 最大最小都在右
  3. 最大左最小右
  4. 最大右最小左

如果都在左或者都在右，可以根据已有的信息算出右端点的位置。$r=l-mx[l]-mi[l]$ 其中 $mx,mi$ 表示从 $mid$ 到 $i$ 的最大/最小值，因为我们要合并中间的信息这样定义比较方便。右侧同理也可以快速算出。

在两侧也类似，这里举一个最大右最小左的例子，从式子 $r-l=mx[r]-mi[l]$ 推出 $mi[l]-l=mx[r]-r$，用桶维护每一个答案的出现次数，如果找到了这样一个值，每次都加上对它的需求量就可以了。

另外一种同理。