【日常小测】巡游计划

题目大意

有$n(n \le 52501)$个城市，依次分布在数轴上
若你到达$i$号城市，则你必须停留$a_i$个单位时间
若你当前在$i$号城市，则你只能前往编号$\in (i,i+k]$的城市
若你在城市$i$，打算前往城市$j$，那么你会花费$|p_i-p_j| \cdot b_i$的时间
现在你从$1$号城市出发，最终到达$n$号城市，问花费的最短时间

解题报告

下面内容建立在你已经会了BZOJ 1492的维护凸壳的做法

先不考虑那个绝对值的限制，显然就是一个斜率DP的形式
我们考虑对序列建一个线段树，每一次得到了$i$号城市的答案后
我们在线段树上进行依次区间加的操作，即将$i$号城市对应的点加入线段树对应结点的凸壳内
因为在线段树上只会被拆分成$O(\log n)$个结点、插入凸壳复杂度$O(\log n)$，于是复杂度为$O(n \log^2 n)$

至于如何查询？我们从左到右依次处理，假设我们当前想得到$i$号城市的答案
那我们在$i$在线段树内对应的节点到根的路径上的每一个凸壳我们都询问一次答案
然后取一个最值就可以了，时间复杂度仍然是$O(n \log^2 n)$的

现在我们考虑绝对值的限制
我们可以钦定$p_i$与$p_j$的大小关系
具体来说，我们在得到$i$号城市的答案后，我们只是将他扔到线段树上去，但先不建立凸包
然后我们对那棵线段树进行中序遍历，那么在走到结点i的时候，我们已经知道了需要查询哪些点，凸壳总共有哪些点
于是我们将这些东西扔到一起，然后排序，然后从小到大遍历一次

如果是查询的点，就到当前的凸壳中更新答案
如果是应该加入到凸壳的点，那就加入到凸壳中
因为已经排过序，所以绝对值可以打开

我们再从大到小再来一遍，这样就可以得到这个结点的所有答案了
不难发现一个点只会被插入凸壳$O(\log n)$次，也只会被查询这么多次
所以时间复杂度仍然为$O(n \log^2 n)$