分治

区间分治

A1

求所有区间最大值之和

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

$$f(n)=f(a)+f(n-a)+O(1)=O(n)$$

算上 ST 表和排序的话复杂度$O(n\log_2n)$。

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

A2

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

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

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

这样我们预处理一下$Lmax_i$表示第$i$个数左边第一个比它大的数的位置。同理处理一下$Lmin,Rmax,Rmin$，它们都可以线性处理，这样上述问题就可以$O(r-l+1)$求解了，总复杂度$O(n\log_2n)$。

A3

求所有区间的 GCD 之和

这道题是可以不分治直接做的。维护一个三元组集合，$(l,r,v)$表示区间$[i,R],l \le i\le r$的$\gcd$为$v$。那么我们从小到大枚举$R$，并计算对应的三元组集合。在同一个时刻$v$只有$O(\log_2V)$种取值，因此集合的大小是$O(\log_2V)$的。而在$R$自増的过程中$v$不会增加，于是整体的均摊复杂度是$O(\log_2n)$的。

要分治的话，强行分一个中点，然后限制左端点和右端点的范围，按照上面的做即可。复杂度$O(n\log_2^2n)$。

A4

给定一个排列$p$，求有几个区间$[L,R]$满足足$\left\langle p_i \right\rangle_{i=L}^R$排序后是连续的。

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

$$\max_{i=L}^Rp_i-\min_{i=L}^Rp_i=R-L$$

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

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

ZJOI2016 旅行者

给定一个$N\times M$的网格图，有$Q$次询问，每询问两点之间的最短路。$n,m\le 2\times 10^4, q\le 10^5$。

切一条中线考虑在左右的点对的最短路。枚举中线上的点$x$，$dis(a,b)=\min(dis(a,b),dis(a,x)+dis(x,b))$，于是直接对中线上的点跑单源最短路即可。设$S=mn$。中线可以横着切，也可以竖着切。因此我们总能找到一种切法使得中线长度小于等于$\sqrt{S}$，因此复杂度分析为

$$f(S)=2f(S/2)+O(S\sqrt S\log_2S) =O(S\sqrt S\log_2S)$$

代码

平面最近点对

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

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

$$f(n)=2f(n/2)+O(6n)=O(n\log_2n)$$