题解 P3642 【[APIO2016]烟火表演】

· · 题解

神仙题目啊QwQ

设f_i(x)表示以第i个点为根的子树需要x秒引爆的代价。

我们发现，这个函数是一个下凸的一次分段函数。

考虑这个函数合并到父亲节点时会发生怎样的变化。

设f_i'(x)是原函数，f_i(x)是新函数，i和父亲之间的边长度为l，[L, R]是f_i'(x)斜率为0的那一段的左右端点的横坐标，那么有：

f_i(x) = \begin{cases}f_i'(x) + l & x \leq L \\f_i'(L) + (l - (x - L)) & L < x \leq L + l \\f_i'(L) & L + l < x \leq R + l \\f_i'(L) + ((x - R) - l) & R + l < x\end{cases}

我们一个一个来看。

首先第一个，当x \leq L时，我们肯定要让新的l越小越好，因为改变l的代价为1，而这个函数在\leq L的时候斜率\leq -1，即修改一次x的代价\geq 1，所以干脆将l变成0。

第二个，我们只要保证x = L就能取到函数的最小值，于是l的变化量越小越好。

第三个，我们不用改变l就可以保证能取到最小值，那就不用改变了。

第四个和第一个很像，这里就略去了。

那么这个过程究竟对这个函数做了什么改变呢？

我们将\leq L部分的函数向上平移了l单位，将[L,R]部分向右平移l单位，在[L,L+l]部分插入了一条斜率为-1的直线，并将> R + l的部分的斜率改为了1。

于是大概变成了这个样子（图源网络）：

这样，各个拐点之间的直线的斜率是从左到右递增的。

我们不妨假设各个拐点之间的直线斜率的增量为1，如果有一个斜率不存在，那么我们就用两个同一位置的拐点来表示这个不存在的斜率。

然后我们发现我们只可能存下拐点的横坐标，于是怎么求函数值是一个问题。

我们如果能知道f(0)的值，这个事情就好办了。

于是我们得到了通过拐点横坐标求得$f(L)$的方法，皆大欢喜。 那么我们知道每个函数被合并上去之前会变成什么样子了，那么我们也可以非常简单的合并两个函数了，我们只需要将两个函数的拐点列表合并一下就可以了。 我们再看看在合并到父亲节点时要做的操作： 一、将斜率$> 0$的那一段的斜率改为$1$。 因为我们合并上来的函数的斜率最大值都为$1$，所以我们只需要删除$k - 1$个最大的拐点即可，其中$k$是这个点儿子的数量。 二、将斜率$=0$的那一段平移$l$单位。 首先，我们做完一操作之后，横坐标最大的两个拐点就是斜率为$0$的两个端点了，将它们弹出来，加上$l$再放进去就没了。 三、加入一段斜率为$-1$的直线。 这个其实在做操作二的时候就顺带做完了。 我们维护一个可并堆就可以做上面的所有操作。 最后求答案时，我们保留$L$及其左边的拐点，依次减去它们的横坐标就是我们想要的函数值了。 代码见我的[$\texttt{blog}$](https://www.cnblogs.com/cj-xxz/p/10631433.html)