区间分治

A1

求所有区间最大值之和

元素从大到小排序,用 ST 表预处理区间最大值的位置,然后按照最大值的位置分治即可。复杂度分析为

算上 ST 表和排序的话复杂度

当然,还可以用并查集解决。

A2

求所有区间的最大值乘最小值的和。

这种不知道怎么搞的题就先一通分治。于是我们就要求跨过的区间的贡献。但这样直接做似乎还不够,于是大力讨论一波:

  1. 最大值最小值都在左边的区间。显然我们可以钦定一个的区间,求出这个区间的最大值和最小值,然后可以想办法求出它往右可以扩张的最大范围,使得的最大值和最小值也是,这样就可以统计贡献了;
  2. 最大值在左边,最小值在右边。我们枚举一个左端点,然后看右端点的取值范围。于是我们找到右边第一个比当前最大值大的数,并且在第一个比最小值小的数之后。然后这部分的最大值乘最小值就可以算了。事实上由于最大值的变化是单调递增的,因此我们右端点也是单调移动的,于是在移动的过程中统计贡献即可;
  3. 剩下两种情况是对称的;
  4. 对于有相同元素的情况,可能要钦定一下最左边的那个是最大的,然后处理一下细节问题,不然可能算重。

这样我们预处理一下表示第个数左边第一个比它大的数的位置。同理处理一下,它们都可以线性处理,这样上述问题就可以求解了,总复杂度

A3

求所有区间的 GCD 之和

这道题是可以不分治直接做的。维护一个三元组集合,表示区间。那么我们从小到大枚举,并计算对应的三元组集合。在同一个时刻只有种取值,因此集合的大小是的。而在自増的过程中不会增加,于是整体的均摊复杂度是的。

要分治的话,强行分一个中点,然后限制左端点和右端点的范围,按照上面的做即可。复杂度

A4

给定一个排列,求有几个区间满足足排序后是连续的。

这题显然可以用析合树直接做。但是大材小用。由于这是一个排列,因此我们要求的就是满足

的区间的个数。于是又可以分类讨论一下:

  1. 最大值最小值在左边。那么我们枚举左端点,则右端点是单调递增的,在移动的过程中判断是否存在有合法的情况(即)。
  2. 最大值在左边,最小值在右边。则我们枚举左端点,然后像 A2 一样如法炮制找到右端点的一段合法区间。于是我们可以获得如下的信息:表示的最小值在右边且为。三元组序列的是非严格单减的。于是我们检查即可判断是否合法。在向左扩展的时候,是非严格递增的。

ZJOI2016 旅行者

给定一个的网格图,有次询问,每询问两点之间的最短路。

切一条中线考虑在左右的点对的最短路。枚举中线上的点,于是直接对中线上的点跑单源最短路即可。设。中线可以横着切,也可以竖着切。因此我们总能找到一种切法使得中线长度小于等于,因此复杂度分析为

代码

平面最近点对

给出平面上个点,求最近的两个点之间的距离。

做平面分治,考虑跨过中线的点对,设当前的答案为。范围缩小到两平行线间。这时我们枚举左边的点,则右边的点的的距离不超过,框出一个大小为的矩形。右边的矩形任意两个点的距离大于等于 d,发现矩形内至多有个点。于是计算距离然后更新即可。复杂度分析为